1 // Copyright 2012 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 "image"
9 )
10 11 // makeImg allocates and initializes the destination image.
12 func (d *decoder) makeImg(mxx, myy int) {
13 if d.nComp == 1 {
14 m := image.NewGray(image.Rect(0, 0, 8*mxx, 8*myy))
15 d.img1 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.Gray)
16 return
17 }
18 19 h0 := d.comp[0].h
20 v0 := d.comp[0].v
21 hRatio := h0 / d.comp[1].h
22 vRatio := v0 / d.comp[1].v
23 var subsampleRatio image.YCbCrSubsampleRatio
24 switch hRatio<<4 | vRatio {
25 case 0x11:
26 subsampleRatio = image.YCbCrSubsampleRatio444
27 case 0x12:
28 subsampleRatio = image.YCbCrSubsampleRatio440
29 case 0x21:
30 subsampleRatio = image.YCbCrSubsampleRatio422
31 case 0x22:
32 subsampleRatio = image.YCbCrSubsampleRatio420
33 case 0x41:
34 subsampleRatio = image.YCbCrSubsampleRatio411
35 case 0x42:
36 subsampleRatio = image.YCbCrSubsampleRatio410
37 default:
38 panic("unreachable")
39 }
40 m := image.NewYCbCr(image.Rect(0, 0, 8*h0*mxx, 8*v0*myy), subsampleRatio)
41 d.img3 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.YCbCr)
42 43 if d.nComp == 4 {
44 h3, v3 := d.comp[3].h, d.comp[3].v
45 d.blackPix = []byte{:8*h3*mxx*8*v3*myy}
46 d.blackStride = 8 * h3 * mxx
47 }
48 }
49 50 // Specified in section B.2.3.
51 func (d *decoder) processSOS(n int) error {
52 if d.nComp == 0 {
53 return FormatError("missing SOF marker")
54 }
55 if n < 6 || 4+2*d.nComp < n || n%2 != 0 {
56 return FormatError("SOS has wrong length")
57 }
58 if err := d.readFull(d.tmp[:n]); err != nil {
59 return err
60 }
61 nComp := int(d.tmp[0])
62 if n != 4+2*nComp {
63 return FormatError("SOS length inconsistent with number of components")
64 }
65 var scan [maxComponents]struct {
66 compIndex uint8
67 td uint8 // DC table selector.
68 ta uint8 // AC table selector.
69 }
70 totalHV := 0
71 for i := 0; i < nComp; i++ {
72 cs := d.tmp[1+2*i] // Component selector.
73 compIndex := -1
74 for j, comp := range d.comp[:d.nComp] {
75 if cs == comp.c {
76 compIndex = j
77 }
78 }
79 if compIndex < 0 {
80 return FormatError("unknown component selector")
81 }
82 scan[i].compIndex = uint8(compIndex)
83 // Section B.2.3 states that "the value of Cs_j shall be different from
84 // the values of Cs_1 through Cs_(j-1)". Since we have previously
85 // verified that a frame's component identifiers (C_i values in section
86 // B.2.2) are unique, it suffices to check that the implicit indexes
87 // into d.comp are unique.
88 for j := 0; j < i; j++ {
89 if scan[i].compIndex == scan[j].compIndex {
90 return FormatError("repeated component selector")
91 }
92 }
93 totalHV += d.comp[compIndex].h * d.comp[compIndex].v
94 95 // The baseline t <= 1 restriction is specified in table B.3.
96 scan[i].td = d.tmp[2+2*i] >> 4
97 if t := scan[i].td; t > maxTh || (d.baseline && t > 1) {
98 return FormatError("bad Td value")
99 }
100 scan[i].ta = d.tmp[2+2*i] & 0x0f
101 if t := scan[i].ta; t > maxTh || (d.baseline && t > 1) {
102 return FormatError("bad Ta value")
103 }
104 }
105 // Section B.2.3 states that if there is more than one component then the
106 // total H*V values in a scan must be <= 10.
107 if d.nComp > 1 && totalHV > 10 {
108 return FormatError("total sampling factors too large")
109 }
110 111 // zigStart and zigEnd are the spectral selection bounds.
112 // ah and al are the successive approximation high and low values.
113 // The spec calls these values Ss, Se, Ah and Al.
114 //
115 // For progressive JPEGs, these are the two more-or-less independent
116 // aspects of progression. Spectral selection progression is when not
117 // all of a block's 64 DCT coefficients are transmitted in one pass.
118 // For example, three passes could transmit coefficient 0 (the DC
119 // component), coefficients 1-5, and coefficients 6-63, in zig-zag
120 // order. Successive approximation is when not all of the bits of a
121 // band of coefficients are transmitted in one pass. For example,
122 // three passes could transmit the 6 most significant bits, followed
123 // by the second-least significant bit, followed by the least
124 // significant bit.
125 //
126 // For sequential JPEGs, these parameters are hard-coded to 0/63/0/0, as
127 // per table B.3.
128 zigStart, zigEnd, ah, al := int32(0), int32(blockSize-1), uint32(0), uint32(0)
129 if d.progressive {
130 zigStart = int32(d.tmp[1+2*nComp])
131 zigEnd = int32(d.tmp[2+2*nComp])
132 ah = uint32(d.tmp[3+2*nComp] >> 4)
133 al = uint32(d.tmp[3+2*nComp] & 0x0f)
134 if (zigStart == 0 && zigEnd != 0) || zigStart > zigEnd || blockSize <= zigEnd {
135 return FormatError("bad spectral selection bounds")
136 }
137 if zigStart != 0 && nComp != 1 {
138 return FormatError("progressive AC coefficients for more than one component")
139 }
140 if ah != 0 && ah != al+1 {
141 return FormatError("bad successive approximation values")
142 }
143 }
144 145 // mxx and myy are the number of MCUs (Minimum Coded Units) in the image.
146 h0, v0 := d.comp[0].h, d.comp[0].v // The h and v values from the Y components.
147 mxx := (d.width + 8*h0 - 1) / (8 * h0)
148 myy := (d.height + 8*v0 - 1) / (8 * v0)
149 if d.img1 == nil && d.img3 == nil {
150 d.makeImg(mxx, myy)
151 }
152 if d.progressive {
153 for i := 0; i < nComp; i++ {
154 compIndex := scan[i].compIndex
155 if d.progCoeffs[compIndex] == nil {
156 d.progCoeffs[compIndex] = []block{:mxx*myy*d.comp[compIndex].h*d.comp[compIndex].v}
157 }
158 }
159 }
160 161 d.bits = bits{}
162 mcu, expectedRST := 0, uint8(rst0Marker)
163 var (
164 // b is the decoded coefficients, in natural (not zig-zag) order.
165 b block
166 dc [maxComponents]int32
167 // bx and by are the location of the current block, in units of 8x8
168 // blocks: the third block in the first row has (bx, by) = (2, 0).
169 bx, by int
170 blockCount int
171 )
172 for my := 0; my < myy; my++ {
173 for mx := 0; mx < mxx; mx++ {
174 for i := 0; i < nComp; i++ {
175 compIndex := scan[i].compIndex
176 hi := d.comp[compIndex].h
177 vi := d.comp[compIndex].v
178 for j := 0; j < hi*vi; j++ {
179 // The blocks are traversed one MCU at a time. For 4:2:0 chroma
180 // subsampling, there are four Y 8x8 blocks in every 16x16 MCU.
181 //
182 // For a sequential 32x16 pixel image, the Y blocks visiting order is:
183 // 0 1 4 5
184 // 2 3 6 7
185 //
186 // For progressive images, the interleaved scans (those with nComp > 1)
187 // are traversed as above, but non-interleaved scans are traversed left
188 // to right, top to bottom:
189 // 0 1 2 3
190 // 4 5 6 7
191 // Only DC scans (zigStart == 0) can be interleaved. AC scans must have
192 // only one component.
193 //
194 // To further complicate matters, for non-interleaved scans, there is no
195 // data for any blocks that are inside the image at the MCU level but
196 // outside the image at the pixel level. For example, a 24x16 pixel 4:2:0
197 // progressive image consists of two 16x16 MCUs. The interleaved scans
198 // will process 8 Y blocks:
199 // 0 1 4 5
200 // 2 3 6 7
201 // The non-interleaved scans will process only 6 Y blocks:
202 // 0 1 2
203 // 3 4 5
204 if nComp != 1 {
205 bx = hi*mx + j%hi
206 by = vi*my + j/hi
207 } else {
208 q := mxx * hi
209 bx = blockCount % q
210 by = blockCount / q
211 blockCount++
212 if bx*8 >= d.width || by*8 >= d.height {
213 continue
214 }
215 }
216 217 // Load the previous partially decoded coefficients, if applicable.
218 if d.progressive {
219 b = d.progCoeffs[compIndex][by*mxx*hi+bx]
220 } else {
221 b = block{}
222 }
223 224 if ah != 0 {
225 if err := d.refine(&b, &d.huff[acTable][scan[i].ta], zigStart, zigEnd, 1<<al); err != nil {
226 return err
227 }
228 } else {
229 zig := zigStart
230 if zig == 0 {
231 zig++
232 // Decode the DC coefficient, as specified in section F.2.2.1.
233 value, err := d.decodeHuffman(&d.huff[dcTable][scan[i].td])
234 if err != nil {
235 return err
236 }
237 if value > 16 {
238 return UnsupportedError("excessive DC component")
239 }
240 dcDelta, err := d.receiveExtend(value)
241 if err != nil {
242 return err
243 }
244 dc[compIndex] += dcDelta
245 b[0] = dc[compIndex] << al
246 }
247 248 if zig <= zigEnd && d.eobRun > 0 {
249 d.eobRun--
250 } else {
251 // Decode the AC coefficients, as specified in section F.2.2.2.
252 huff := &d.huff[acTable][scan[i].ta]
253 for ; zig <= zigEnd; zig++ {
254 value, err := d.decodeHuffman(huff)
255 if err != nil {
256 return err
257 }
258 val0 := value >> 4
259 val1 := value & 0x0f
260 if val1 != 0 {
261 zig += int32(val0)
262 if zig > zigEnd {
263 break
264 }
265 ac, err := d.receiveExtend(val1)
266 if err != nil {
267 return err
268 }
269 b[unzig[zig]] = ac << al
270 } else {
271 if val0 != 0x0f {
272 d.eobRun = uint16(1 << val0)
273 if val0 != 0 {
274 bits, err := d.decodeBits(int32(val0))
275 if err != nil {
276 return err
277 }
278 d.eobRun |= uint16(bits)
279 }
280 d.eobRun--
281 break
282 }
283 zig += 0x0f
284 }
285 }
286 }
287 }
288 289 if d.progressive {
290 // Save the coefficients.
291 d.progCoeffs[compIndex][by*mxx*hi+bx] = b
292 // At this point, we could call reconstructBlock to dequantize and perform the
293 // inverse DCT, to save early stages of a progressive image to the *image.YCbCr
294 // buffers (the whole point of progressive encoding), but in Go, the jpeg.Decode
295 // function does not return until the entire image is decoded, so we "continue"
296 // here to avoid wasted computation. Instead, reconstructBlock is called on each
297 // accumulated block by the reconstructProgressiveImage method after all of the
298 // SOS markers are processed.
299 continue
300 }
301 if err := d.reconstructBlock(&b, bx, by, int(compIndex)); err != nil {
302 return err
303 }
304 } // for j
305 } // for i
306 mcu++
307 if d.ri > 0 && mcu%d.ri == 0 && mcu < mxx*myy {
308 // For well-formed input, the RST[0-7] restart marker follows
309 // immediately. For corrupt input, call findRST to try to
310 // resynchronize.
311 if err := d.readFull(d.tmp[:2]); err != nil {
312 return err
313 } else if d.tmp[0] != 0xff || d.tmp[1] != expectedRST {
314 if err := d.findRST(expectedRST); err != nil {
315 return err
316 }
317 }
318 expectedRST++
319 if expectedRST == rst7Marker+1 {
320 expectedRST = rst0Marker
321 }
322 // Reset the Huffman decoder.
323 d.bits = bits{}
324 // Reset the DC components, as per section F.2.1.3.1.
325 dc = [maxComponents]int32{}
326 // Reset the progressive decoder state, as per section G.1.2.2.
327 d.eobRun = 0
328 }
329 } // for mx
330 } // for my
331 332 return nil
333 }
334 335 // refine decodes a successive approximation refinement block, as specified in
336 // section G.1.2.
337 func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int32) error {
338 // Refining a DC component is trivial.
339 if zigStart == 0 {
340 if zigEnd != 0 {
341 panic("unreachable")
342 }
343 bit, err := d.decodeBit()
344 if err != nil {
345 return err
346 }
347 if bit {
348 b[0] |= delta
349 }
350 return nil
351 }
352 353 // Refining AC components is more complicated; see sections G.1.2.2 and G.1.2.3.
354 zig := zigStart
355 if d.eobRun == 0 {
356 loop:
357 for ; zig <= zigEnd; zig++ {
358 z := int32(0)
359 value, err := d.decodeHuffman(h)
360 if err != nil {
361 return err
362 }
363 val0 := value >> 4
364 val1 := value & 0x0f
365 366 switch val1 {
367 case 0:
368 if val0 != 0x0f {
369 d.eobRun = uint16(1 << val0)
370 if val0 != 0 {
371 bits, err := d.decodeBits(int32(val0))
372 if err != nil {
373 return err
374 }
375 d.eobRun |= uint16(bits)
376 }
377 break loop
378 }
379 case 1:
380 z = delta
381 bit, err := d.decodeBit()
382 if err != nil {
383 return err
384 }
385 if !bit {
386 z = -z
387 }
388 default:
389 return FormatError("unexpected Huffman code")
390 }
391 392 zig, err = d.refineNonZeroes(b, zig, zigEnd, int32(val0), delta)
393 if err != nil {
394 return err
395 }
396 if zig > zigEnd {
397 return FormatError("too many coefficients")
398 }
399 if z != 0 {
400 b[unzig[zig]] = z
401 }
402 }
403 }
404 if d.eobRun > 0 {
405 d.eobRun--
406 if _, err := d.refineNonZeroes(b, zig, zigEnd, -1, delta); err != nil {
407 return err
408 }
409 }
410 return nil
411 }
412 413 // refineNonZeroes refines non-zero entries of b in zig-zag order. If nz >= 0,
414 // the first nz zero entries are skipped over.
415 func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int32) (int32, error) {
416 for ; zig <= zigEnd; zig++ {
417 u := unzig[zig]
418 if b[u] == 0 {
419 if nz == 0 {
420 break
421 }
422 nz--
423 continue
424 }
425 bit, err := d.decodeBit()
426 if err != nil {
427 return 0, err
428 }
429 if !bit {
430 continue
431 }
432 if b[u] >= 0 {
433 b[u] += delta
434 } else {
435 b[u] -= delta
436 }
437 }
438 return zig, nil
439 }
440 441 func (d *decoder) reconstructProgressiveImage() error {
442 // The h0, mxx, by and bx variables have the same meaning as in the
443 // processSOS method.
444 h0 := d.comp[0].h
445 mxx := (d.width + 8*h0 - 1) / (8 * h0)
446 for i := 0; i < d.nComp; i++ {
447 if d.progCoeffs[i] == nil {
448 continue
449 }
450 v := 8 * d.comp[0].v / d.comp[i].v
451 h := 8 * d.comp[0].h / d.comp[i].h
452 stride := mxx * d.comp[i].h
453 for by := 0; by*v < d.height; by++ {
454 for bx := 0; bx*h < d.width; bx++ {
455 if err := d.reconstructBlock(&d.progCoeffs[i][by*stride+bx], bx, by, i); err != nil {
456 return err
457 }
458 }
459 }
460 }
461 return nil
462 }
463 464 // reconstructBlock dequantizes, performs the inverse DCT and stores the block
465 // to the image.
466 func (d *decoder) reconstructBlock(b *block, bx, by, compIndex int) error {
467 qt := &d.quant[d.comp[compIndex].tq]
468 for zig := 0; zig < blockSize; zig++ {
469 b[unzig[zig]] *= qt[zig]
470 }
471 idct(b)
472 dst, stride := []byte(nil), 0
473 if d.nComp == 1 {
474 dst, stride = d.img1.Pix[8*(by*d.img1.Stride+bx):], d.img1.Stride
475 } else {
476 switch compIndex {
477 case 0:
478 dst, stride = d.img3.Y[8*(by*d.img3.YStride+bx):], d.img3.YStride
479 case 1:
480 dst, stride = d.img3.Cb[8*(by*d.img3.CStride+bx):], d.img3.CStride
481 case 2:
482 dst, stride = d.img3.Cr[8*(by*d.img3.CStride+bx):], d.img3.CStride
483 case 3:
484 dst, stride = d.blackPix[8*(by*d.blackStride+bx):], d.blackStride
485 default:
486 return UnsupportedError("too many components")
487 }
488 }
489 // Level shift by +128, clip to [0, 255], and write to dst.
490 for y := 0; y < 8; y++ {
491 y8 := y * 8
492 yStride := y * stride
493 for x := 0; x < 8; x++ {
494 c := b[y8+x]
495 if c < -128 {
496 c = 0
497 } else if c > 127 {
498 c = 255
499 } else {
500 c += 128
501 }
502 dst[yStride+x] = uint8(c)
503 }
504 }
505 return nil
506 }
507 508 // findRST advances past the next RST restart marker that matches expectedRST.
509 // Other than I/O errors, it is also an error if we encounter an {0xFF, M}
510 // two-byte marker sequence where M is not 0x00, 0xFF or the expectedRST.
511 //
512 // This is similar to libjpeg's jdmarker.c's next_marker function.
513 // https://github.com/libjpeg-turbo/libjpeg-turbo/blob/2dfe6c0fe9e18671105e94f7cbf044d4a1d157e6/jdmarker.c#L892-L935
514 //
515 // Precondition: d.tmp[:2] holds the next two bytes of JPEG-encoded input
516 // (input in the d.readFull sense).
517 func (d *decoder) findRST(expectedRST uint8) error {
518 for {
519 // i is the index such that, at the bottom of the loop, we read 2-i
520 // bytes into d.tmp[i:2], maintaining the invariant that d.tmp[:2]
521 // holds the next two bytes of JPEG-encoded input. It is either 0 or 1,
522 // so that each iteration advances by 1 or 2 bytes (or returns).
523 i := 0
524 525 if d.tmp[0] == 0xff {
526 if d.tmp[1] == expectedRST {
527 return nil
528 } else if d.tmp[1] == 0xff {
529 i = 1
530 } else if d.tmp[1] != 0x00 {
531 // libjpeg's jdmarker.c's jpeg_resync_to_restart does something
532 // fancy here, treating RST markers within two (modulo 8) of
533 // expectedRST differently from RST markers that are 'more
534 // distant'. Until we see evidence that recovering from such
535 // cases is frequent enough to be worth the complexity, we take
536 // a simpler approach for now. Any marker that's not 0x00, 0xff
537 // or expectedRST is a fatal FormatError.
538 return FormatError("bad RST marker")
539 }
540 541 } else if d.tmp[1] == 0xff {
542 d.tmp[0] = 0xff
543 i = 1
544 }
545 546 if err := d.readFull(d.tmp[i:2]); err != nil {
547 return err
548 }
549 }
550 }
551