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 }