Source file src/pkg/image/jpeg/writer.go
1 // Copyright 2011 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package jpeg 6 7 import ( 8 "bufio" 9 "errors" 10 "image" 11 "image/color" 12 "io" 13 ) 14 15 // min returns the minimum of two integers. 16 func min(x, y int) int { 17 if x < y { 18 return x 19 } 20 return y 21 } 22 23 // div returns a/b rounded to the nearest integer, instead of rounded to zero. 24 func div(a int, b int) int { 25 if a >= 0 { 26 return (a + (b >> 1)) / b 27 } 28 return -((-a + (b >> 1)) / b) 29 } 30 31 // bitCount counts the number of bits needed to hold an integer. 32 var bitCount = [256]byte{ 33 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 34 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 35 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 36 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 37 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 38 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 39 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 40 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 41 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 42 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 43 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 44 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 45 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 46 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 47 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 48 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 49 } 50 51 type quantIndex int 52 53 const ( 54 quantIndexLuminance quantIndex = iota 55 quantIndexChrominance 56 nQuantIndex 57 ) 58 59 // unscaledQuant are the unscaled quantization tables. Each encoder copies and 60 // scales the tables according to its quality parameter. 61 var unscaledQuant = [nQuantIndex][blockSize]byte{ 62 // Luminance. 63 { 64 16, 11, 10, 16, 24, 40, 51, 61, 65 12, 12, 14, 19, 26, 58, 60, 55, 66 14, 13, 16, 24, 40, 57, 69, 56, 67 14, 17, 22, 29, 51, 87, 80, 62, 68 18, 22, 37, 56, 68, 109, 103, 77, 69 24, 35, 55, 64, 81, 104, 113, 92, 70 49, 64, 78, 87, 103, 121, 120, 101, 71 72, 92, 95, 98, 112, 100, 103, 99, 72 }, 73 // Chrominance. 74 { 75 17, 18, 24, 47, 99, 99, 99, 99, 76 18, 21, 26, 66, 99, 99, 99, 99, 77 24, 26, 56, 99, 99, 99, 99, 99, 78 47, 66, 99, 99, 99, 99, 99, 99, 79 99, 99, 99, 99, 99, 99, 99, 99, 80 99, 99, 99, 99, 99, 99, 99, 99, 81 99, 99, 99, 99, 99, 99, 99, 99, 82 99, 99, 99, 99, 99, 99, 99, 99, 83 }, 84 } 85 86 type huffIndex int 87 88 const ( 89 huffIndexLuminanceDC huffIndex = iota 90 huffIndexLuminanceAC 91 huffIndexChrominanceDC 92 huffIndexChrominanceAC 93 nHuffIndex 94 ) 95 96 // huffmanSpec specifies a Huffman encoding. 97 type huffmanSpec struct { 98 // count[i] is the number of codes of length i bits. 99 count [16]byte 100 // value[i] is the decoded value of the i'th codeword. 101 value []byte 102 } 103 104 // theHuffmanSpec is the Huffman encoding specifications. 105 // This encoder uses the same Huffman encoding for all images. 106 var theHuffmanSpec = [nHuffIndex]huffmanSpec{ 107 // Luminance DC. 108 { 109 [16]byte{0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}, 110 []byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 111 }, 112 // Luminance AC. 113 { 114 [16]byte{0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 125}, 115 []byte{ 116 0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12, 117 0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61, 0x07, 118 0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08, 119 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52, 0xd1, 0xf0, 120 0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0a, 0x16, 121 0x17, 0x18, 0x19, 0x1a, 0x25, 0x26, 0x27, 0x28, 122 0x29, 0x2a, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 123 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 124 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 125 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 126 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 127 0x7a, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 128 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 129 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 130 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 131 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5, 132 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, 0xd3, 0xd4, 133 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2, 134 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 135 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 136 0xf9, 0xfa, 137 }, 138 }, 139 // Chrominance DC. 140 { 141 [16]byte{0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, 142 []byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 143 }, 144 // Chrominance AC. 145 { 146 [16]byte{0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 119}, 147 []byte{ 148 0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21, 149 0x31, 0x06, 0x12, 0x41, 0x51, 0x07, 0x61, 0x71, 150 0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91, 151 0xa1, 0xb1, 0xc1, 0x09, 0x23, 0x33, 0x52, 0xf0, 152 0x15, 0x62, 0x72, 0xd1, 0x0a, 0x16, 0x24, 0x34, 153 0xe1, 0x25, 0xf1, 0x17, 0x18, 0x19, 0x1a, 0x26, 154 0x27, 0x28, 0x29, 0x2a, 0x35, 0x36, 0x37, 0x38, 155 0x39, 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 156 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 157 0x59, 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 158 0x69, 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 159 0x79, 0x7a, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 160 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 161 0x97, 0x98, 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 162 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 163 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 164 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, 165 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 166 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 167 0xea, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 168 0xf9, 0xfa, 169 }, 170 }, 171 } 172 173 // huffmanLUT is a compiled look-up table representation of a huffmanSpec. 174 // Each value maps to a uint32 of which the 8 most significant bits hold the 175 // codeword size in bits and the 24 least significant bits hold the codeword. 176 // The maximum codeword size is 16 bits. 177 type huffmanLUT []uint32 178 179 func (h *huffmanLUT) init(s huffmanSpec) { 180 maxValue := 0 181 for _, v := range s.value { 182 if int(v) > maxValue { 183 maxValue = int(v) 184 } 185 } 186 *h = make([]uint32, maxValue+1) 187 code, k := uint32(0), 0 188 for i := 0; i < len(s.count); i++ { 189 nBits := uint32(i+1) << 24 190 for j := uint8(0); j < s.count[i]; j++ { 191 (*h)[s.value[k]] = nBits | code 192 code++ 193 k++ 194 } 195 code <<= 1 196 } 197 } 198 199 // theHuffmanLUT are compiled representations of theHuffmanSpec. 200 var theHuffmanLUT [4]huffmanLUT 201 202 func init() { 203 for i, s := range theHuffmanSpec { 204 theHuffmanLUT[i].init(s) 205 } 206 } 207 208 // writer is a buffered writer. 209 type writer interface { 210 Flush() error 211 Write([]byte) (int, error) 212 WriteByte(byte) error 213 } 214 215 // encoder encodes an image to the JPEG format. 216 type encoder struct { 217 // w is the writer to write to. err is the first error encountered during 218 // writing. All attempted writes after the first error become no-ops. 219 w writer 220 err error 221 // buf is a scratch buffer. 222 buf [16]byte 223 // bits and nBits are accumulated bits to write to w. 224 bits, nBits uint32 225 // quant is the scaled quantization tables. 226 quant [nQuantIndex][blockSize]byte 227 } 228 229 func (e *encoder) flush() { 230 if e.err != nil { 231 return 232 } 233 e.err = e.w.Flush() 234 } 235 236 func (e *encoder) write(p []byte) { 237 if e.err != nil { 238 return 239 } 240 _, e.err = e.w.Write(p) 241 } 242 243 func (e *encoder) writeByte(b byte) { 244 if e.err != nil { 245 return 246 } 247 e.err = e.w.WriteByte(b) 248 } 249 250 // emit emits the least significant nBits bits of bits to the bitstream. 251 // The precondition is bits < 1<<nBits && nBits <= 16. 252 func (e *encoder) emit(bits, nBits uint32) { 253 nBits += e.nBits 254 bits <<= 32 - nBits 255 bits |= e.bits 256 for nBits >= 8 { 257 b := uint8(bits >> 24) 258 e.writeByte(b) 259 if b == 0xff { 260 e.writeByte(0x00) 261 } 262 bits <<= 8 263 nBits -= 8 264 } 265 e.bits, e.nBits = bits, nBits 266 } 267 268 // emitHuff emits the given value with the given Huffman encoder. 269 func (e *encoder) emitHuff(h huffIndex, value int) { 270 x := theHuffmanLUT[h][value] 271 e.emit(x&(1<<24-1), x>>24) 272 } 273 274 // emitHuffRLE emits a run of runLength copies of value encoded with the given 275 // Huffman encoder. 276 func (e *encoder) emitHuffRLE(h huffIndex, runLength, value int) { 277 a, b := value, value 278 if a < 0 { 279 a, b = -value, value-1 280 } 281 var nBits uint32 282 if a < 0x100 { 283 nBits = uint32(bitCount[a]) 284 } else { 285 nBits = 8 + uint32(bitCount[a>>8]) 286 } 287 e.emitHuff(h, runLength<<4|int(nBits)) 288 if nBits > 0 { 289 e.emit(uint32(b)&(1<<nBits-1), nBits) 290 } 291 } 292 293 // writeMarkerHeader writes the header for a marker with the given length. 294 func (e *encoder) writeMarkerHeader(marker uint8, markerlen int) { 295 e.buf[0] = 0xff 296 e.buf[1] = marker 297 e.buf[2] = uint8(markerlen >> 8) 298 e.buf[3] = uint8(markerlen & 0xff) 299 e.write(e.buf[:4]) 300 } 301 302 // writeDQT writes the Define Quantization Table marker. 303 func (e *encoder) writeDQT() { 304 markerlen := 2 + int(nQuantIndex)*(1+blockSize) 305 e.writeMarkerHeader(dqtMarker, markerlen) 306 for i := range e.quant { 307 e.writeByte(uint8(i)) 308 e.write(e.quant[i][:]) 309 } 310 } 311 312 // writeSOF0 writes the Start Of Frame (Baseline) marker. 313 func (e *encoder) writeSOF0(size image.Point) { 314 markerlen := 8 + 3*nColorComponent 315 e.writeMarkerHeader(sof0Marker, markerlen) 316 e.buf[0] = 8 // 8-bit color. 317 e.buf[1] = uint8(size.Y >> 8) 318 e.buf[2] = uint8(size.Y & 0xff) 319 e.buf[3] = uint8(size.X >> 8) 320 e.buf[4] = uint8(size.X & 0xff) 321 e.buf[5] = nColorComponent 322 for i := 0; i < nColorComponent; i++ { 323 e.buf[3*i+6] = uint8(i + 1) 324 // We use 4:2:0 chroma subsampling. 325 e.buf[3*i+7] = "\x22\x11\x11"[i] 326 e.buf[3*i+8] = "\x00\x01\x01"[i] 327 } 328 e.write(e.buf[:3*(nColorComponent-1)+9]) 329 } 330 331 // writeDHT writes the Define Huffman Table marker. 332 func (e *encoder) writeDHT() { 333 markerlen := 2 334 for _, s := range theHuffmanSpec { 335 markerlen += 1 + 16 + len(s.value) 336 } 337 e.writeMarkerHeader(dhtMarker, markerlen) 338 for i, s := range theHuffmanSpec { 339 e.writeByte("\x00\x10\x01\x11"[i]) 340 e.write(s.count[:]) 341 e.write(s.value) 342 } 343 } 344 345 // writeBlock writes a block of pixel data using the given quantization table, 346 // returning the post-quantized DC value of the DCT-transformed block. 347 func (e *encoder) writeBlock(b *block, q quantIndex, prevDC int) int { 348 fdct(b) 349 // Emit the DC delta. 350 dc := div(b[0], (8 * int(e.quant[q][0]))) 351 e.emitHuffRLE(huffIndex(2*q+0), 0, dc-prevDC) 352 // Emit the AC components. 353 h, runLength := huffIndex(2*q+1), 0 354 for k := 1; k < blockSize; k++ { 355 ac := div(b[unzig[k]], (8 * int(e.quant[q][k]))) 356 if ac == 0 { 357 runLength++ 358 } else { 359 for runLength > 15 { 360 e.emitHuff(h, 0xf0) 361 runLength -= 16 362 } 363 e.emitHuffRLE(h, runLength, ac) 364 runLength = 0 365 } 366 } 367 if runLength > 0 { 368 e.emitHuff(h, 0x00) 369 } 370 return dc 371 } 372 373 // toYCbCr converts the 8x8 region of m whose top-left corner is p to its 374 // YCbCr values. 375 func toYCbCr(m image.Image, p image.Point, yBlock, cbBlock, crBlock *block) { 376 b := m.Bounds() 377 xmax := b.Max.X - 1 378 ymax := b.Max.Y - 1 379 for j := 0; j < 8; j++ { 380 for i := 0; i < 8; i++ { 381 r, g, b, _ := m.At(min(p.X+i, xmax), min(p.Y+j, ymax)).RGBA() 382 yy, cb, cr := color.RGBToYCbCr(uint8(r>>8), uint8(g>>8), uint8(b>>8)) 383 yBlock[8*j+i] = int(yy) 384 cbBlock[8*j+i] = int(cb) 385 crBlock[8*j+i] = int(cr) 386 } 387 } 388 } 389 390 // rgbaToYCbCr is a specialized version of toYCbCr for image.RGBA images. 391 func rgbaToYCbCr(m *image.RGBA, p image.Point, yBlock, cbBlock, crBlock *block) { 392 b := m.Bounds() 393 xmax := b.Max.X - 1 394 ymax := b.Max.Y - 1 395 for j := 0; j < 8; j++ { 396 sj := p.Y + j 397 if sj > ymax { 398 sj = ymax 399 } 400 offset := (sj-b.Min.Y)*m.Stride - b.Min.X*4 401 for i := 0; i < 8; i++ { 402 sx := p.X + i 403 if sx > xmax { 404 sx = xmax 405 } 406 pix := m.Pix[offset+sx*4:] 407 yy, cb, cr := color.RGBToYCbCr(pix[0], pix[1], pix[2]) 408 yBlock[8*j+i] = int(yy) 409 cbBlock[8*j+i] = int(cb) 410 crBlock[8*j+i] = int(cr) 411 } 412 } 413 } 414 415 // scale scales the 16x16 region represented by the 4 src blocks to the 8x8 416 // dst block. 417 func scale(dst *block, src *[4]block) { 418 for i := 0; i < 4; i++ { 419 dstOff := (i&2)<<4 | (i&1)<<2 420 for y := 0; y < 4; y++ { 421 for x := 0; x < 4; x++ { 422 j := 16*y + 2*x 423 sum := src[i][j] + src[i][j+1] + src[i][j+8] + src[i][j+9] 424 dst[8*y+x+dstOff] = (sum + 2) >> 2 425 } 426 } 427 } 428 } 429 430 // sosHeader is the SOS marker "\xff\xda" followed by 12 bytes: 431 // - the marker length "\x00\x0c", 432 // - the number of components "\x03", 433 // - component 1 uses DC table 0 and AC table 0 "\x01\x00", 434 // - component 2 uses DC table 1 and AC table 1 "\x02\x11", 435 // - component 3 uses DC table 1 and AC table 1 "\x03\x11", 436 // - padding "\x00\x00\x00". 437 var sosHeader = []byte{ 438 0xff, 0xda, 0x00, 0x0c, 0x03, 0x01, 0x00, 0x02, 439 0x11, 0x03, 0x11, 0x00, 0x00, 0x00, 440 } 441 442 // writeSOS writes the StartOfScan marker. 443 func (e *encoder) writeSOS(m image.Image) { 444 e.write(sosHeader) 445 var ( 446 // Scratch buffers to hold the YCbCr values. 447 yBlock block 448 cbBlock [4]block 449 crBlock [4]block 450 cBlock block 451 // DC components are delta-encoded. 452 prevDCY, prevDCCb, prevDCCr int 453 ) 454 bounds := m.Bounds() 455 rgba, _ := m.(*image.RGBA) 456 for y := bounds.Min.Y; y < bounds.Max.Y; y += 16 { 457 for x := bounds.Min.X; x < bounds.Max.X; x += 16 { 458 for i := 0; i < 4; i++ { 459 xOff := (i & 1) * 8 460 yOff := (i & 2) * 4 461 p := image.Pt(x+xOff, y+yOff) 462 if rgba != nil { 463 rgbaToYCbCr(rgba, p, &yBlock, &cbBlock[i], &crBlock[i]) 464 } else { 465 toYCbCr(m, p, &yBlock, &cbBlock[i], &crBlock[i]) 466 } 467 prevDCY = e.writeBlock(&yBlock, 0, prevDCY) 468 } 469 scale(&cBlock, &cbBlock) 470 prevDCCb = e.writeBlock(&cBlock, 1, prevDCCb) 471 scale(&cBlock, &crBlock) 472 prevDCCr = e.writeBlock(&cBlock, 1, prevDCCr) 473 } 474 } 475 // Pad the last byte with 1's. 476 e.emit(0x7f, 7) 477 } 478 479 // DefaultQuality is the default quality encoding parameter. 480 const DefaultQuality = 75 481 482 // Options are the encoding parameters. 483 // Quality ranges from 1 to 100 inclusive, higher is better. 484 type Options struct { 485 Quality int 486 } 487 488 // Encode writes the Image m to w in JPEG 4:2:0 baseline format with the given 489 // options. Default parameters are used if a nil *Options is passed. 490 func Encode(w io.Writer, m image.Image, o *Options) error { 491 b := m.Bounds() 492 if b.Dx() >= 1<<16 || b.Dy() >= 1<<16 { 493 return errors.New("jpeg: image is too large to encode") 494 } 495 var e encoder 496 if ww, ok := w.(writer); ok { 497 e.w = ww 498 } else { 499 e.w = bufio.NewWriter(w) 500 } 501 // Clip quality to [1, 100]. 502 quality := DefaultQuality 503 if o != nil { 504 quality = o.Quality 505 if quality < 1 { 506 quality = 1 507 } else if quality > 100 { 508 quality = 100 509 } 510 } 511 // Convert from a quality rating to a scaling factor. 512 var scale int 513 if quality < 50 { 514 scale = 5000 / quality 515 } else { 516 scale = 200 - quality*2 517 } 518 // Initialize the quantization tables. 519 for i := range e.quant { 520 for j := range e.quant[i] { 521 x := int(unscaledQuant[i][j]) 522 x = (x*scale + 50) / 100 523 if x < 1 { 524 x = 1 525 } else if x > 255 { 526 x = 255 527 } 528 e.quant[i][j] = uint8(x) 529 } 530 } 531 // Write the Start Of Image marker. 532 e.buf[0] = 0xff 533 e.buf[1] = 0xd8 534 e.write(e.buf[:2]) 535 // Write the quantization tables. 536 e.writeDQT() 537 // Write the image dimensions. 538 e.writeSOF0(b.Size()) 539 // Write the Huffman tables. 540 e.writeDHT() 541 // Write the image data. 542 e.writeSOS(m) 543 // Write the End Of Image marker. 544 e.buf[0] = 0xff 545 e.buf[1] = 0xd9 546 e.write(e.buf[:2]) 547 e.flush() 548 return e.err 549 }