Rebase.

[official-gcc.git] / libgo / go / image / jpeg / scan.go

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package jpeg

import (
        "image"
        "io"
)

// makeImg allocates and initializes the destination image.
func (d *decoder) makeImg(h0, v0, mxx, myy int) {
        if d.nComp == nGrayComponent {
                m := image.NewGray(image.Rect(0, 0, 8*mxx, 8*myy))
                d.img1 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.Gray)
                return
        }
        var subsampleRatio image.YCbCrSubsampleRatio
        switch {
        case h0 == 1 && v0 == 1:
                subsampleRatio = image.YCbCrSubsampleRatio444
        case h0 == 1 && v0 == 2:
                subsampleRatio = image.YCbCrSubsampleRatio440
        case h0 == 2 && v0 == 1:
                subsampleRatio = image.YCbCrSubsampleRatio422
        case h0 == 2 && v0 == 2:
                subsampleRatio = image.YCbCrSubsampleRatio420
        default:
                panic("unreachable")
        }
        m := image.NewYCbCr(image.Rect(0, 0, 8*h0*mxx, 8*v0*myy), subsampleRatio)
        d.img3 = m.SubImage(image.Rect(0, 0, d.width, d.height)).(*image.YCbCr)
}

// Specified in section B.2.3.
func (d *decoder) processSOS(n int) error {
        if d.nComp == 0 {
                return FormatError("missing SOF marker")
        }
        if n < 6 || 4+2*d.nComp < n || n%2 != 0 {
                return FormatError("SOS has wrong length")
        }
        _, err := io.ReadFull(d.r, d.tmp[:n])
        if err != nil {
                return err
        }
        nComp := int(d.tmp[0])
        if n != 4+2*nComp {
                return FormatError("SOS length inconsistent with number of components")
        }
        var scan [nColorComponent]struct {
                compIndex uint8
                td        uint8 // DC table selector.
                ta        uint8 // AC table selector.
        }
        for i := 0; i < nComp; i++ {
                cs := d.tmp[1+2*i] // Component selector.
                compIndex := -1
                for j, comp := range d.comp {
                        if cs == comp.c {
                                compIndex = j
                        }
                }
                if compIndex < 0 {
                        return FormatError("unknown component selector")
                }
                scan[i].compIndex = uint8(compIndex)
                scan[i].td = d.tmp[2+2*i] >> 4
                scan[i].ta = d.tmp[2+2*i] & 0x0f
        }

        // zigStart and zigEnd are the spectral selection bounds.
        // ah and al are the successive approximation high and low values.
        // The spec calls these values Ss, Se, Ah and Al.
        //
        // For progressive JPEGs, these are the two more-or-less independent
        // aspects of progression. Spectral selection progression is when not
        // all of a block's 64 DCT coefficients are transmitted in one pass.
        // For example, three passes could transmit coefficient 0 (the DC
        // component), coefficients 1-5, and coefficients 6-63, in zig-zag
        // order. Successive approximation is when not all of the bits of a
        // band of coefficients are transmitted in one pass. For example,
        // three passes could transmit the 6 most significant bits, followed
        // by the second-least significant bit, followed by the least
        // significant bit.
        //
        // For baseline JPEGs, these parameters are hard-coded to 0/63/0/0.
        zigStart, zigEnd, ah, al := int32(0), int32(blockSize-1), uint32(0), uint32(0)
        if d.progressive {
                zigStart = int32(d.tmp[1+2*nComp])
                zigEnd = int32(d.tmp[2+2*nComp])
                ah = uint32(d.tmp[3+2*nComp] >> 4)
                al = uint32(d.tmp[3+2*nComp] & 0x0f)
                if (zigStart == 0 && zigEnd != 0) || zigStart > zigEnd || blockSize <= zigEnd {
                        return FormatError("bad spectral selection bounds")
                }
                if zigStart != 0 && nComp != 1 {
                        return FormatError("progressive AC coefficients for more than one component")
                }
                if ah != 0 && ah != al+1 {
                        return FormatError("bad successive approximation values")
                }
        }

        // mxx and myy are the number of MCUs (Minimum Coded Units) in the image.
        h0, v0 := d.comp[0].h, d.comp[0].v // The h and v values from the Y components.
        mxx := (d.width + 8*h0 - 1) / (8 * h0)
        myy := (d.height + 8*v0 - 1) / (8 * v0)
        if d.img1 == nil && d.img3 == nil {
                d.makeImg(h0, v0, mxx, myy)
        }
        if d.progressive {
                for i := 0; i < nComp; i++ {
                        compIndex := scan[i].compIndex
                        if d.progCoeffs[compIndex] == nil {
                                d.progCoeffs[compIndex] = make([]block, mxx*myy*d.comp[compIndex].h*d.comp[compIndex].v)
                        }
                }
        }

        d.b = bits{}
        mcu, expectedRST := 0, uint8(rst0Marker)
        var (
                // b is the decoded coefficients, in natural (not zig-zag) order.
                b  block
                dc [nColorComponent]int32
                // mx0 and my0 are the location of the current (in terms of 8x8 blocks).
                // For example, with 4:2:0 chroma subsampling, the block whose top left
                // pixel co-ordinates are (16, 8) is the third block in the first row:
                // mx0 is 2 and my0 is 0, even though the pixel is in the second MCU.
                // TODO(nigeltao): rename mx0 and my0 to bx and by?
                mx0, my0   int
                blockCount int
        )
        for my := 0; my < myy; my++ {
                for mx := 0; mx < mxx; mx++ {
                        for i := 0; i < nComp; i++ {
                                compIndex := scan[i].compIndex
                                qt := &d.quant[d.comp[compIndex].tq]
                                for j := 0; j < d.comp[compIndex].h*d.comp[compIndex].v; j++ {
                                        // The blocks are traversed one MCU at a time. For 4:2:0 chroma
                                        // subsampling, there are four Y 8x8 blocks in every 16x16 MCU.
                                        //
                                        // For a baseline 32x16 pixel image, the Y blocks visiting order is:
                                        //      0 1 4 5
                                        //      2 3 6 7
                                        //
                                        // For progressive images, the interleaved scans (those with nComp > 1)
                                        // are traversed as above, but non-interleaved scans are traversed left
                                        // to right, top to bottom:
                                        //      0 1 2 3
                                        //      4 5 6 7
                                        // Only DC scans (zigStart == 0) can be interleaved. AC scans must have
                                        // only one component.
                                        //
                                        // To further complicate matters, for non-interleaved scans, there is no
                                        // data for any blocks that are inside the image at the MCU level but
                                        // outside the image at the pixel level. For example, a 24x16 pixel 4:2:0
                                        // progressive image consists of two 16x16 MCUs. The interleaved scans
                                        // will process 8 Y blocks:
                                        //      0 1 4 5
                                        //      2 3 6 7
                                        // The non-interleaved scans will process only 6 Y blocks:
                                        //      0 1 2
                                        //      3 4 5
                                        if nComp != 1 {
                                                mx0, my0 = d.comp[compIndex].h*mx, d.comp[compIndex].v*my
                                                if h0 == 1 {
                                                        my0 += j
                                                } else {
                                                        mx0 += j % 2
                                                        my0 += j / 2
                                                }
                                        } else {
                                                q := mxx * d.comp[compIndex].h
                                                mx0 = blockCount % q
                                                my0 = blockCount / q
                                                blockCount++
                                                if mx0*8 >= d.width || my0*8 >= d.height {
                                                        continue
                                                }
                                        }

                                        // Load the previous partially decoded coefficients, if applicable.
                                        if d.progressive {
                                                b = d.progCoeffs[compIndex][my0*mxx*d.comp[compIndex].h+mx0]
                                        } else {
                                                b = block{}
                                        }

                                        if ah != 0 {
                                                if err := d.refine(&b, &d.huff[acTable][scan[i].ta], zigStart, zigEnd, 1<<al); err != nil {
                                                        return err
                                                }
                                        } else {
                                                zig := zigStart
                                                if zig == 0 {
                                                        zig++
                                                        // Decode the DC coefficient, as specified in section F.2.2.1.
                                                        value, err := d.decodeHuffman(&d.huff[dcTable][scan[i].td])
                                                        if err != nil {
                                                                return err
                                                        }
                                                        if value > 16 {
                                                                return UnsupportedError("excessive DC component")
                                                        }
                                                        dcDelta, err := d.receiveExtend(value)
                                                        if err != nil {
                                                                return err
                                                        }
                                                        dc[compIndex] += dcDelta
                                                        b[0] = dc[compIndex] << al
                                                }

                                                if zig <= zigEnd && d.eobRun > 0 {
                                                        d.eobRun--
                                                } else {
                                                        // Decode the AC coefficients, as specified in section F.2.2.2.
                                                        for ; zig <= zigEnd; zig++ {
                                                                value, err := d.decodeHuffman(&d.huff[acTable][scan[i].ta])
                                                                if err != nil {
                                                                        return err
                                                                }
                                                                val0 := value >> 4
                                                                val1 := value & 0x0f
                                                                if val1 != 0 {
                                                                        zig += int32(val0)
                                                                        if zig > zigEnd {
                                                                                break
                                                                        }
                                                                        ac, err := d.receiveExtend(val1)
                                                                        if err != nil {
                                                                                return err
                                                                        }
                                                                        b[unzig[zig]] = ac << al
                                                                } else {
                                                                        if val0 != 0x0f {
                                                                                d.eobRun = uint16(1 << val0)
                                                                                if val0 != 0 {
                                                                                        bits, err := d.decodeBits(int(val0))
                                                                                        if err != nil {
                                                                                                return err
                                                                                        }
                                                                                        d.eobRun |= uint16(bits)
                                                                                }
                                                                                d.eobRun--
                                                                                break
                                                                        }
                                                                        zig += 0x0f
                                                                }
                                                        }
                                                }
                                        }

                                        if d.progressive {
                                                if zigEnd != blockSize-1 || al != 0 {
                                                        // We haven't completely decoded this 8x8 block. Save the coefficients.
                                                        d.progCoeffs[compIndex][my0*mxx*d.comp[compIndex].h+mx0] = b
                                                        // At this point, we could execute the rest of the loop body to dequantize and
                                                        // perform the inverse DCT, to save early stages of a progressive image to the
                                                        // *image.YCbCr buffers (the whole point of progressive encoding), but in Go,
                                                        // the jpeg.Decode function does not return until the entire image is decoded,
                                                        // so we "continue" here to avoid wasted computation.
                                                        continue
                                                }
                                        }

                                        // Dequantize, perform the inverse DCT and store the block to the image.
                                        for zig := 0; zig < blockSize; zig++ {
                                                b[unzig[zig]] *= qt[zig]
                                        }
                                        idct(&b)
                                        dst, stride := []byte(nil), 0
                                        if d.nComp == nGrayComponent {
                                                dst, stride = d.img1.Pix[8*(my0*d.img1.Stride+mx0):], d.img1.Stride
                                        } else {
                                                switch compIndex {
                                                case 0:
                                                        dst, stride = d.img3.Y[8*(my0*d.img3.YStride+mx0):], d.img3.YStride
                                                case 1:
                                                        dst, stride = d.img3.Cb[8*(my0*d.img3.CStride+mx0):], d.img3.CStride
                                                case 2:
                                                        dst, stride = d.img3.Cr[8*(my0*d.img3.CStride+mx0):], d.img3.CStride
                                                default:
                                                        return UnsupportedError("too many components")
                                                }
                                        }
                                        // Level shift by +128, clip to [0, 255], and write to dst.
                                        for y := 0; y < 8; y++ {
                                                y8 := y * 8
                                                yStride := y * stride
                                                for x := 0; x < 8; x++ {
                                                        c := b[y8+x]
                                                        if c < -128 {
                                                                c = 0
                                                        } else if c > 127 {
                                                                c = 255
                                                        } else {
                                                                c += 128
                                                        }
                                                        dst[yStride+x] = uint8(c)
                                                }
                                        }
                                } // for j
                        } // for i
                        mcu++
                        if d.ri > 0 && mcu%d.ri == 0 && mcu < mxx*myy {
                                // A more sophisticated decoder could use RST[0-7] markers to resynchronize from corrupt input,
                                // but this one assumes well-formed input, and hence the restart marker follows immediately.
                                _, err := io.ReadFull(d.r, d.tmp[0:2])
                                if err != nil {
                                        return err
                                }
                                if d.tmp[0] != 0xff || d.tmp[1] != expectedRST {
                                        return FormatError("bad RST marker")
                                }
                                expectedRST++
                                if expectedRST == rst7Marker+1 {
                                        expectedRST = rst0Marker
                                }
                                // Reset the Huffman decoder.
                                d.b = bits{}
                                // Reset the DC components, as per section F.2.1.3.1.
                                dc = [nColorComponent]int32{}
                                // Reset the progressive decoder state, as per section G.1.2.2.
                                d.eobRun = 0
                        }
                } // for mx
        } // for my

        return nil
}

// refine decodes a successive approximation refinement block, as specified in
// section G.1.2.
func (d *decoder) refine(b *block, h *huffman, zigStart, zigEnd, delta int32) error {
        // Refining a DC component is trivial.
        if zigStart == 0 {
                if zigEnd != 0 {
                        panic("unreachable")
                }
                bit, err := d.decodeBit()
                if err != nil {
                        return err
                }
                if bit {
                        b[0] |= delta
                }
                return nil
        }

        // Refining AC components is more complicated; see sections G.1.2.2 and G.1.2.3.
        zig := zigStart
        if d.eobRun == 0 {
        loop:
                for ; zig <= zigEnd; zig++ {
                        z := int32(0)
                        value, err := d.decodeHuffman(h)
                        if err != nil {
                                return err
                        }
                        val0 := value >> 4
                        val1 := value & 0x0f

                        switch val1 {
                        case 0:
                                if val0 != 0x0f {
                                        d.eobRun = uint16(1 << val0)
                                        if val0 != 0 {
                                                bits, err := d.decodeBits(int(val0))
                                                if err != nil {
                                                        return err
                                                }
                                                d.eobRun |= uint16(bits)
                                        }
                                        break loop
                                }
                        case 1:
                                z = delta
                                bit, err := d.decodeBit()
                                if err != nil {
                                        return err
                                }
                                if !bit {
                                        z = -z
                                }
                        default:
                                return FormatError("unexpected Huffman code")
                        }

                        zig, err = d.refineNonZeroes(b, zig, zigEnd, int32(val0), delta)
                        if err != nil {
                                return err
                        }
                        if zig > zigEnd {
                                return FormatError("too many coefficients")
                        }
                        if z != 0 {
                                b[unzig[zig]] = z
                        }
                }
        }
        if d.eobRun > 0 {
                d.eobRun--
                if _, err := d.refineNonZeroes(b, zig, zigEnd, -1, delta); err != nil {
                        return err
                }
        }
        return nil
}

// refineNonZeroes refines non-zero entries of b in zig-zag order. If nz >= 0,
// the first nz zero entries are skipped over.
func (d *decoder) refineNonZeroes(b *block, zig, zigEnd, nz, delta int32) (int32, error) {
        for ; zig <= zigEnd; zig++ {
                u := unzig[zig]
                if b[u] == 0 {
                        if nz == 0 {
                                break
                        }
                        nz--
                        continue
                }
                bit, err := d.decodeBit()
                if err != nil {
                        return 0, err
                }
                if !bit {
                        continue
                }
                if b[u] >= 0 {
                        b[u] += delta
                } else {
                        b[u] -= delta
                }
        }
        return zig, nil
}