image/jpeg: fix quantization tables to be in zig-zag order, not natural
order.
JPEG images generated prior to this CL are still valid JPEGs, as the
quantization tables used are encoded in the wire format. Such JPEGs just
don't use the recommended quantization tables.
R=r, dsymonds, raph, adg
CC=golang-dev, tuom.larsen
https://golang.org/cl/6497083
diff --git a/src/pkg/image/jpeg/reader.go b/src/pkg/image/jpeg/reader.go
index bf67b7e..652dc5f 100644
--- a/src/pkg/image/jpeg/reader.go
+++ b/src/pkg/image/jpeg/reader.go
@@ -74,7 +74,9 @@
comMarker = 0xfe // COMment.
)
-// Maps from the zig-zag ordering to the natural ordering.
+// unzig maps from the zig-zag ordering to the natural ordering. For example,
+// unzig[3] is the column and row of the fourth element in zig-zag order. The
+// value is 16, which means first column (16%8 == 0) and third row (16/8 == 2).
var unzig = [blockSize]int{
0, 1, 8, 16, 9, 2, 3, 10,
17, 24, 32, 25, 18, 11, 4, 5,
@@ -101,7 +103,7 @@
nComp int
comp [nColorComponent]component
huff [maxTc + 1][maxTh + 1]huffman
- quant [maxTq + 1]block
+ quant [maxTq + 1]block // Quantization tables, in zig-zag order.
b bits
tmp [1024]byte
}
@@ -266,6 +268,7 @@
for j := 0; j < d.comp[i].h*d.comp[i].v; j++ {
// TODO(nigeltao): make this a "var b block" once the compiler's escape
// analysis is good enough to allocate it on the stack, not the heap.
+ // b is in natural (not zig-zag) order.
b = block{}
// Decode the DC coefficient, as specified in section F.2.2.1.
@@ -284,7 +287,7 @@
b[0] = dc[i] * qt[0]
// Decode the AC coefficients, as specified in section F.2.2.2.
- for k := 1; k < blockSize; k++ {
+ for zig := 1; zig < blockSize; zig++ {
value, err := d.decodeHuffman(&d.huff[acTable][scan[i].ta])
if err != nil {
return err
@@ -292,20 +295,20 @@
val0 := value >> 4
val1 := value & 0x0f
if val1 != 0 {
- k += int(val0)
- if k > blockSize {
+ zig += int(val0)
+ if zig > blockSize {
return FormatError("bad DCT index")
}
ac, err := d.receiveExtend(val1)
if err != nil {
return err
}
- b[unzig[k]] = ac * qt[k]
+ b[unzig[zig]] = ac * qt[zig]
} else {
if val0 != 0x0f {
break
}
- k += 0x0f
+ zig += 0x0f
}
}
diff --git a/src/pkg/image/jpeg/writer.go b/src/pkg/image/jpeg/writer.go
index d539b1d..099298e 100644
--- a/src/pkg/image/jpeg/writer.go
+++ b/src/pkg/image/jpeg/writer.go
@@ -56,26 +56,28 @@
nQuantIndex
)
-// unscaledQuant are the unscaled quantization tables. Each encoder copies and
-// scales the tables according to its quality parameter.
+// unscaledQuant are the unscaled quantization tables in zig-zag order. Each
+// encoder copies and scales the tables according to its quality parameter.
+// The values are derived from section K.1 after converting from natural to
+// zig-zag order.
var unscaledQuant = [nQuantIndex][blockSize]byte{
// Luminance.
{
- 16, 11, 10, 16, 24, 40, 51, 61,
- 12, 12, 14, 19, 26, 58, 60, 55,
- 14, 13, 16, 24, 40, 57, 69, 56,
- 14, 17, 22, 29, 51, 87, 80, 62,
- 18, 22, 37, 56, 68, 109, 103, 77,
- 24, 35, 55, 64, 81, 104, 113, 92,
- 49, 64, 78, 87, 103, 121, 120, 101,
- 72, 92, 95, 98, 112, 100, 103, 99,
+ 16, 11, 12, 14, 12, 10, 16, 14,
+ 13, 14, 18, 17, 16, 19, 24, 40,
+ 26, 24, 22, 22, 24, 49, 35, 37,
+ 29, 40, 58, 51, 61, 60, 57, 51,
+ 56, 55, 64, 72, 92, 78, 64, 68,
+ 87, 69, 55, 56, 80, 109, 81, 87,
+ 95, 98, 103, 104, 103, 62, 77, 113,
+ 121, 112, 100, 120, 92, 101, 103, 99,
},
// Chrominance.
{
- 17, 18, 24, 47, 99, 99, 99, 99,
- 18, 21, 26, 66, 99, 99, 99, 99,
- 24, 26, 56, 99, 99, 99, 99, 99,
- 47, 66, 99, 99, 99, 99, 99, 99,
+ 17, 18, 18, 24, 21, 24, 47, 26,
+ 26, 47, 99, 66, 56, 66, 99, 99,
+ 99, 99, 99, 99, 99, 99, 99, 99,
+ 99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
@@ -222,7 +224,7 @@
buf [16]byte
// bits and nBits are accumulated bits to write to w.
bits, nBits uint32
- // quant is the scaled quantization tables.
+ // quant is the scaled quantization tables, in zig-zag order.
quant [nQuantIndex][blockSize]byte
}
@@ -301,7 +303,7 @@
// writeDQT writes the Define Quantization Table marker.
func (e *encoder) writeDQT() {
- markerlen := 2 + int(nQuantIndex)*(1+blockSize)
+ const markerlen = 2 + int(nQuantIndex)*(1+blockSize)
e.writeMarkerHeader(dqtMarker, markerlen)
for i := range e.quant {
e.writeByte(uint8(i))
@@ -311,7 +313,7 @@
// writeSOF0 writes the Start Of Frame (Baseline) marker.
func (e *encoder) writeSOF0(size image.Point) {
- markerlen := 8 + 3*nColorComponent
+ const markerlen = 8 + 3*nColorComponent
e.writeMarkerHeader(sof0Marker, markerlen)
e.buf[0] = 8 // 8-bit color.
e.buf[1] = uint8(size.Y >> 8)
@@ -344,6 +346,7 @@
// writeBlock writes a block of pixel data using the given quantization table,
// returning the post-quantized DC value of the DCT-transformed block.
+// b is in natural (not zig-zag) order.
func (e *encoder) writeBlock(b *block, q quantIndex, prevDC int) int {
fdct(b)
// Emit the DC delta.
@@ -351,8 +354,8 @@
e.emitHuffRLE(huffIndex(2*q+0), 0, dc-prevDC)
// Emit the AC components.
h, runLength := huffIndex(2*q+1), 0
- for k := 1; k < blockSize; k++ {
- ac := div(b[unzig[k]], (8 * int(e.quant[q][k])))
+ for zig := 1; zig < blockSize; zig++ {
+ ac := div(b[unzig[zig]], (8 * int(e.quant[q][zig])))
if ac == 0 {
runLength++
} else {
@@ -446,6 +449,7 @@
e.write(sosHeader)
var (
// Scratch buffers to hold the YCbCr values.
+ // The blocks are in natural (not zig-zag) order.
yBlock block
cbBlock [4]block
crBlock [4]block
diff --git a/src/pkg/image/jpeg/writer_test.go b/src/pkg/image/jpeg/writer_test.go
index b8e8fa3..8732df8 100644
--- a/src/pkg/image/jpeg/writer_test.go
+++ b/src/pkg/image/jpeg/writer_test.go
@@ -6,6 +6,7 @@
import (
"bytes"
+ "fmt"
"image"
"image/color"
"image/png"
@@ -15,6 +16,87 @@
"testing"
)
+// zigzag maps from the natural ordering to the zig-zag ordering. For example,
+// zigzag[0*8 + 3] is the zig-zag sequence number of the element in the fourth
+// column and first row.
+var zigzag = [blockSize]int{
+ 0, 1, 5, 6, 14, 15, 27, 28,
+ 2, 4, 7, 13, 16, 26, 29, 42,
+ 3, 8, 12, 17, 25, 30, 41, 43,
+ 9, 11, 18, 24, 31, 40, 44, 53,
+ 10, 19, 23, 32, 39, 45, 52, 54,
+ 20, 22, 33, 38, 46, 51, 55, 60,
+ 21, 34, 37, 47, 50, 56, 59, 61,
+ 35, 36, 48, 49, 57, 58, 62, 63,
+}
+
+func TestZigUnzig(t *testing.T) {
+ for i := 0; i < blockSize; i++ {
+ if unzig[zigzag[i]] != i {
+ t.Errorf("unzig[zigzag[%d]] == %d", i, unzig[zigzag[i]])
+ }
+ if zigzag[unzig[i]] != i {
+ t.Errorf("zigzag[unzig[%d]] == %d", i, zigzag[unzig[i]])
+ }
+ }
+}
+
+// unscaledQuantInNaturalOrder are the unscaled quantization tables in
+// natural (not zig-zag) order, as specified in section K.1.
+var unscaledQuantInNaturalOrder = [nQuantIndex][blockSize]byte{
+ // Luminance.
+ {
+ 16, 11, 10, 16, 24, 40, 51, 61,
+ 12, 12, 14, 19, 26, 58, 60, 55,
+ 14, 13, 16, 24, 40, 57, 69, 56,
+ 14, 17, 22, 29, 51, 87, 80, 62,
+ 18, 22, 37, 56, 68, 109, 103, 77,
+ 24, 35, 55, 64, 81, 104, 113, 92,
+ 49, 64, 78, 87, 103, 121, 120, 101,
+ 72, 92, 95, 98, 112, 100, 103, 99,
+ },
+ // Chrominance.
+ {
+ 17, 18, 24, 47, 99, 99, 99, 99,
+ 18, 21, 26, 66, 99, 99, 99, 99,
+ 24, 26, 56, 99, 99, 99, 99, 99,
+ 47, 66, 99, 99, 99, 99, 99, 99,
+ 99, 99, 99, 99, 99, 99, 99, 99,
+ 99, 99, 99, 99, 99, 99, 99, 99,
+ 99, 99, 99, 99, 99, 99, 99, 99,
+ 99, 99, 99, 99, 99, 99, 99, 99,
+ },
+}
+
+func TestUnscaledQuant(t *testing.T) {
+ bad := false
+ for i := quantIndex(0); i < nQuantIndex; i++ {
+ for zig := 0; zig < blockSize; zig++ {
+ got := unscaledQuant[i][zig]
+ want := unscaledQuantInNaturalOrder[i][unzig[zig]]
+ if got != want {
+ t.Errorf("i=%d, zig=%d: got %d, want %d", i, zig, got, want)
+ bad = true
+ }
+ }
+ }
+ if bad {
+ names := [nQuantIndex]string{"Luminance", "Chrominance"}
+ buf := &bytes.Buffer{}
+ for i, name := range names {
+ fmt.Fprintf(buf, "// %s.\n{\n", name)
+ for zig := 0; zig < blockSize; zig++ {
+ fmt.Fprintf(buf, "%d, ", unscaledQuantInNaturalOrder[i][unzig[zig]])
+ if zig%8 == 7 {
+ buf.WriteString("\n")
+ }
+ }
+ buf.WriteString("},\n")
+ }
+ t.Logf("expected unscaledQuant values:\n%s", buf.String())
+ }
+}
+
var testCase = []struct {
filename string
quality int
