code review 164056: Basic image/jpeg decoder.

Basic image/jpeg decoder.

This is not a complete JPEG implementation (e.g. it does not handle
progressive JPEGs or restart markers), but I was able to take a photo
with my phone, and view the resultant JPEG in pure Go.

The decoder is simple, but slow. The Huffman decoder in particular
should be easily improvable, but optimization is left to future
changelists. Being able to inline functions in the inner loop should
also help performance.

The output is not pixel-for-pixel identical to libjpeg, although
identical behavior isn't necessarily a goal, since JPEG is a lossy
codec. There are at least two reasons for the discrepancy.

First, the inverse DCT algorithm used is the same as Plan9's
src/cmd/jpg, which has different rounding errors from libjpeg's
default IDCT implementation. Note that libjpeg actually has three
different IDCT implementations: one floating point, and two fixed
point. Out of those four, Plan9's seemed the simplest to understand,
partly because it has no #ifdef's or C macros.

Second, for 4:2:2 or 4:2:0 chroma sampling, this implementation does
nearest neighbor upsampling, compared to libjpeg's triangle filter
(e.g. see h2v1_fancy_upsample in jdsample.c).

The difference from the first reason is typically zero, but sometimes
1 (out of 256) in YCbCr space, or double that in RGB space. The
difference from the second reason can be as large as 8/256 in YCbCr
space, in regions of steep chroma gradients. Informal eyeballing
suggests that the net difference is typically imperceptible, though.

[nigeltao, 2009-12-01 07:11:03]

Hello r, rsc (cc: golang-dev@googlegroups.com),

I'd like you to review the following change.

[r, 2009-12-02 00:44:02]

nice code

a few quick comments from pass 1

http://codereview.appspot.com/164056/diff/7/1008
File src/pkg/image/jpeg/huffman.go (right):

http://codereview.appspot.com/164056/diff/7/1008#newcode33
src/pkg/image/jpeg/huffman.go:33: minCode, maxCode	[maxCodeLength]int;	//
min/max codes of length i, or -1 if no codes of that length.
if you split these into two lines the layout will improve.

http://codereview.appspot.com/164056/diff/7/1009
File src/pkg/image/jpeg/idct.go (right):

http://codereview.appspot.com/164056/diff/7/1009#newcode20
src/pkg/image/jpeg/idct.go:20: w3mw5	= 799;	// w3-w5
might as well use the expressions instead of evaluating them yourself in these
latter cases.

http://codereview.appspot.com/164056/diff/7/1009#newcode32
src/pkg/image/jpeg/idct.go:32: // for the discrete Fourier transform", IEEE
Trans. on ASSP, Vol. ASSP- 32, pp. 803-816, Aug. 1984.
if this is more-or-less directly taken from the plan 9 decoder, it should have a
different copyright. if not, it's ok.

http://codereview.appspot.com/164056/diff/7/1010
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/7/1010#newcode67
src/pkg/image/jpeg/reader.go:67: type Reader interface {
call this ByteReader or ReadByter

http://codereview.appspot.com/164056/diff/7/1010#newcode111
src/pkg/image/jpeg/reader.go:111: return UnsupportedError("precision")
these would be nice if they included the erroneous value.  might want to
functionalize this error type to allow printing to it. unsupportedError() could
be like printf but return an UnsupportedError

http://codereview.appspot.com/164056/diff/7/1010#newcode348
src/pkg/image/jpeg/reader.go:348: if marker == 0xd9 {	// EOI (End Of Image).
make the markers named constants

http://codereview.appspot.com/164056/diff/7/1010#newcode374
src/pkg/image/jpeg/reader.go:374: case (marker >= 0xe0 && marker <= 0xef) ||
marker == 0xfe:	// APPn (application specific) or COM (comment).
did gofmt put in the parens? anyway they're unnecessary

[nigeltao, 2009-12-02 12:08:49]

http://codereview.appspot.com/164056/diff/7/1008
File src/pkg/image/jpeg/huffman.go (right):

http://codereview.appspot.com/164056/diff/7/1008#newcode33
src/pkg/image/jpeg/huffman.go:33: minCode, maxCode	[maxCodeLength]int;	//
min/max codes of length i, or -1 if no codes of that length.
On 2009/12/02 00:44:02, r wrote:
> if you split these into two lines the layout will improve.

Done.

http://codereview.appspot.com/164056/diff/7/1009
File src/pkg/image/jpeg/idct.go (right):

http://codereview.appspot.com/164056/diff/7/1009#newcode20
src/pkg/image/jpeg/idct.go:20: w3mw5	= 799;	// w3-w5
On 2009/12/02 00:44:02, r wrote:
> might as well use the expressions instead of evaluating them yourself in these
> latter cases.

Done.

http://codereview.appspot.com/164056/diff/7/1009#newcode32
src/pkg/image/jpeg/idct.go:32: // for the discrete Fourier transform", IEEE
Trans. on ASSP, Vol. ASSP- 32, pp. 803-816, Aug. 1984.
On 2009/12/02 00:44:02, r wrote:
> if this is more-or-less directly taken from the plan 9 decoder, it should have
a
> different copyright. if not, it's ok.

This is more-or-less directly taken from the Plan 9 decoder:
http://www.google.com/codesearch/p?hl=en#kYwBl4fvuWY/pub/FreeBSD/distfiles/pl...
readjpg.c&l=1510

The LICENSE file in the plan9port tarball gives the "Lucent Public License
Version 1.02" (which is online at
http://plan9.bell-labs.com/plan9/license.html), and also says:
"Copyright © 2000-2009 Lucent Technologies.  All Rights Reserved.
Portions Copyright © 2001-2008 Russ Cox
Portions Copyright © 2008-2009 Google Inc."

(Yeah, I feel stupid telling either of you about Plan 9, but it's for
completeness).


I am not a lawyer. What's the process from here?

Do we leave the code as is, but replace the copyright and license comment in
lines 1-3? If so, what would we need to say, and do we need to note that
anywhere else? If not, how do we get an IDCT implementation?

Should we ask somebody like cdibona?

http://codereview.appspot.com/164056/diff/7/1010
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/7/1010#newcode54
src/pkg/image/jpeg/reader.go:54: // TODO(nigeltao): check with r/rsc that this
has to be a var, and can't be a const.
It is var, not const, right?

http://codereview.appspot.com/164056/diff/7/1010#newcode67
src/pkg/image/jpeg/reader.go:67: type Reader interface {
On 2009/12/02 00:44:02, r wrote:
> call this ByteReader or ReadByter

Not BufferedReader?

Note that pkg/compress/flate/inflate.go declares the same interface (just called
Reader). Should this interface live in bufio instead?

http://codereview.appspot.com/164056/diff/7/1010#newcode111
src/pkg/image/jpeg/reader.go:111: return UnsupportedError("precision")
On 2009/12/02 00:44:02, r wrote:
> these would be nice if they included the erroneous value.  might want to
> functionalize this error type to allow printing to it. unsupportedError()
could
> be like printf but return an UnsupportedError

Would such a tiny function be worth it? How about
return UnsupportedError(fmt.Sprintf("precision (%d)", d.tmp[0]));
instead?

http://codereview.appspot.com/164056/diff/7/1010#newcode348
src/pkg/image/jpeg/reader.go:348: if marker == 0xd9 {	// EOI (End Of Image).
On 2009/12/02 00:44:02, r wrote:
> make the markers named constants

Done.

http://codereview.appspot.com/164056/diff/7/1010#newcode374
src/pkg/image/jpeg/reader.go:374: case (marker >= 0xe0 && marker <= 0xef) ||
marker == 0xfe:	// APPn (application specific) or COM (comment).
On 2009/12/02 00:44:02, r wrote:
> did gofmt put in the parens? anyway they're unnecessary

I habitually add unnecessary parentheses because I (and possibly others) can
never remember the precedence of binary operators, except that * beats +. If you
insist, I'll take them out.

[rsc, 2009-12-02 19:30:19]

regarding idct.go.

the code may be via plan 9's jpg but is not of plan 9.
it originated here: http://tinyurl.com/ylporj7
and there are many many copies in various
software packages that have lost the notice.
please use this header in the file:

// Copyright 2009 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.

// This is a Go translation of idct.c from
//
//
http://standards.iso.org/ittf/PubliclyAvailableStandards/ISO_IEC_13818-4_2004...
//
// which carries the following notice:

/* Copyright (C) 1996, MPEG Software Simulation Group. All Rights Reserved. */

/*
 * Disclaimer of Warranty
 *
 * These software programs are available to the user without any license fee or
 * royalty on an "as is" basis.  The MPEG Software Simulation Group disclaims
 * any and all warranties, whether express, implied, or statuary, including any
 * implied warranties or merchantability or of fitness for a particular
 * purpose.  In no event shall the copyright-holder be liable for any
 * incidental, punitive, or consequential damages of any kind whatsoever
 * arising from the use of these programs.
 *
 * This disclaimer of warranty extends to the user of these programs and user's
 * customers, employees, agents, transferees, successors, and assigns.
 *
 * The MPEG Software Simulation Group does not represent or warrant that the
 * programs furnished hereunder are free of infringement of any third-party
 * patents.
 *
 * Commercial implementations of MPEG-1 and MPEG-2 video, including shareware,
 * are subject to royalty fees to patent holders.  Many of these patents are
 * general enough such that they are unavoidable regardless of implementation
 * design.
 *
 */

[nigeltao, 2009-12-02 23:17:15]

On 2009/12/02 19:30:19, rsc wrote:
> please use this header in the file:

Done.

[rsc, 2009-12-02 23:25:57]

a few small nits.  i am leaving the
real review for r.

http://codereview.appspot.com/164056/diff/22/1022
File src/pkg/image/jpeg/huffman.go (right):

http://codereview.appspot.com/164056/diff/22/1022#newcode45
src/pkg/image/jpeg/huffman.go:45: d.b.a = (d.b.a << 8) | int(c);
drop () here

http://codereview.appspot.com/164056/diff/22/1024
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/22/1024#newcode7
src/pkg/image/jpeg/reader.go:7: // The JPEG specification (ISO/IEC 10918-1:1994,
ITU-T T.81) is at http://www.w3.org/Graphics/JPEG/itu-t81.pdf
Most of the other packages like this move the links out of the package comment:

// The jpeg package implements a decoder for JPEG images, as defined in ITU-T
T.81.
package jpeg

// See http://www.w3.org/Graphics/JPEG/itu-t81.pdf

[r2, 2009-12-07 23:15:55]

nigel, have you addressed rsc's comments and uploaded?

[nigeltao, 2009-12-07 23:27:59]

http://codereview.appspot.com/164056/diff/7/1010
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/7/1010#newcode374
src/pkg/image/jpeg/reader.go:374: case (marker >= 0xe0 && marker <= 0xef) ||
marker == 0xfe:	// APPn (application specific) or COM (comment).
On 2009/12/02 12:08:49, nigeltao_golang wrote:
> On 2009/12/02 00:44:02, r wrote:
> > did gofmt put in the parens? anyway they're unnecessary
> 
> I habitually add unnecessary parentheses because I (and possibly others) can
> never remember the precedence of binary operators, except that * beats +. If
you
> insist, I'll take them out.

On second thoughts, I've just taken the parens out.

http://codereview.appspot.com/164056/diff/22/1022
File src/pkg/image/jpeg/huffman.go (right):

http://codereview.appspot.com/164056/diff/22/1022#newcode45
src/pkg/image/jpeg/huffman.go:45: d.b.a = (d.b.a << 8) | int(c);
On 2009/12/02 23:25:57, rsc wrote:
> drop () here
> 

Done.

http://codereview.appspot.com/164056/diff/22/1024
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/22/1024#newcode7
src/pkg/image/jpeg/reader.go:7: // The JPEG specification (ISO/IEC 10918-1:1994,
ITU-T T.81) is at http://www.w3.org/Graphics/JPEG/itu-t81.pdf
On 2009/12/02 23:25:57, rsc wrote:
> Most of the other packages like this move the links out of the package
comment:
> 
> // The jpeg package implements a decoder for JPEG images, as defined in ITU-T
> T.81.
> package jpeg
> 
> // See http://www.w3.org/Graphics/JPEG/itu-t81.pdf

Done.

[r, 2009-12-07 23:40:23]

another round

http://codereview.appspot.com/164056/diff/22/1024
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/22/1024#newcode7
src/pkg/image/jpeg/reader.go:7: // The JPEG specification (ISO/IEC 10918-1:1994,
ITU-T T.81) is at http://www.w3.org/Graphics/JPEG/itu-t81.pdf
yes, put the link outside the package comment.

http://codereview.appspot.com/164056/diff/2002/2005
File src/pkg/image/jpeg/huffman.go (right):

http://codereview.appspot.com/164056/diff/2002/2005#newcode39
src/pkg/image/jpeg/huffman.go:39: func (d *decoder) ensureNumBits(t int)
os.Error {
how about ensureNBits.  NumBits sounds like.... 
and then make the parameter n

http://codereview.appspot.com/164056/diff/2002/2005#newcode99
src/pkg/image/jpeg/huffman.go:99: if th > maxTh || (isBaseline && th > 1) {
parens not needed

http://codereview.appspot.com/164056/diff/2002/2005#newcode118
src/pkg/image/jpeg/huffman.go:118: return FormatError("DHT length")
DHT has wrong length

again, all these messages would benefit from more information. on the other hand
we'll only see them when debugging, so it's probably not worth it

http://codereview.appspot.com/164056/diff/2002/2006
File src/pkg/image/jpeg/idct.go (right):

http://codereview.appspot.com/164056/diff/2002/2006#newcode66
src/pkg/image/jpeg/idct.go:66: func idct(b []int) {
can you make this *b[64] int?  it would mean a lot of range checks could be
optimized away

http://codereview.appspot.com/164056/diff/2002/2007
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/2002/2007#newcode105
src/pkg/image/jpeg/reader.go:105: if err != nil {
fold these lines together

http://codereview.appspot.com/164056/diff/2002/2007#newcode129
src/pkg/image/jpeg/reader.go:129: return UnsupportedError("number of image
components")
same error in two places: bad idea. even just (1) and (2) might help debug

http://codereview.appspot.com/164056/diff/2002/2007#newcode146
src/pkg/image/jpeg/reader.go:146: return UnsupportedError("downsample ratio")
ditto

http://codereview.appspot.com/164056/diff/2002/2007#newcode209
src/pkg/image/jpeg/reader.go:209: d.image.Pixel[py][px] =
image.RGBAColor{uint8(r), uint8(g), uint8(b), 0xff};
this won't be the fastest code out there but it's fine for now

http://codereview.appspot.com/164056/diff/2002/2007#newcode323
src/pkg/image/jpeg/reader.go:323: idct(d.blocks[i][j][0:dctSize2]);
see comment in  idct.go

http://codereview.appspot.com/164056/diff/2002/2007#newcode354
src/pkg/image/jpeg/reader.go:354: if err != nil {
fold lines together

http://codereview.appspot.com/164056/diff/2002/2007#newcode358
src/pkg/image/jpeg/reader.go:358: return nil, FormatError("not a JPEG file")
again, same error two places

[nigeltao, 2009-12-08 13:45:12]

http://codereview.appspot.com/164056/diff/22/1024
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/22/1024#newcode7
src/pkg/image/jpeg/reader.go:7: // The JPEG specification (ISO/IEC 10918-1:1994,
ITU-T T.81) is at http://www.w3.org/Graphics/JPEG/itu-t81.pdf
On 2009/12/07 23:40:23, r wrote:
> yes, put the link outside the package comment.

Done. Should I make the analogous change for image/png (in a separate
changelist)?

http://codereview.appspot.com/164056/diff/2002/2005
File src/pkg/image/jpeg/huffman.go (right):

http://codereview.appspot.com/164056/diff/2002/2005#newcode39
src/pkg/image/jpeg/huffman.go:39: func (d *decoder) ensureNumBits(t int)
os.Error {
On 2009/12/07 23:40:23, r wrote:
> how about ensureNBits.  NumBits sounds like.... 
> and then make the parameter n

Done.

http://codereview.appspot.com/164056/diff/2002/2005#newcode99
src/pkg/image/jpeg/huffman.go:99: if th > maxTh || (isBaseline && th > 1) {
On 2009/12/07 23:40:23, r wrote:
> parens not needed

Done.

http://codereview.appspot.com/164056/diff/2002/2005#newcode118
src/pkg/image/jpeg/huffman.go:118: return FormatError("DHT length")
On 2009/12/07 23:40:23, r wrote:
> DHT has wrong length

I've added the "has wrong", and again on line 87.


> again, all these messages would benefit from more information. on the other
hand
> we'll only see them when debugging, so it's probably not worth it

OK, I've left it as is.

http://codereview.appspot.com/164056/diff/2002/2006
File src/pkg/image/jpeg/idct.go (right):

http://codereview.appspot.com/164056/diff/2002/2006#newcode66
src/pkg/image/jpeg/idct.go:66: func idct(b []int) {
On 2009/12/07 23:40:23, r wrote:
> can you make this *b[64] int?  it would mean a lot of range checks could be
> optimized away

Done.

http://codereview.appspot.com/164056/diff/2002/2007
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/2002/2007#newcode105
src/pkg/image/jpeg/reader.go:105: if err != nil {
On 2009/12/07 23:40:23, r wrote:
> fold these lines together

By "these lines" I assume you mean

_, err := foo();
if err != nil {

instead of

if err != nil {
  return err
}

because if I fold the latter three lines into one, gofmt unfolds them.

But for the former -- do you want me to rewrite all

"x, err := foo();\nif err != nil {"s

in this changelist to

"if x, err := foo(); err != nil {"?

Or only when x is _? Or only for the two places you've explicitly made a "fold
these lines together" comment?

I'm happy to have a consistent style, I'm just not sure what that style should
be.

http://codereview.appspot.com/164056/diff/2002/2007#newcode129
src/pkg/image/jpeg/reader.go:129: return UnsupportedError("number of image
components")
On 2009/12/07 23:40:23, r wrote:
> same error in two places: bad idea. even just (1) and (2) might help debug

Done.

http://codereview.appspot.com/164056/diff/2002/2007#newcode146
src/pkg/image/jpeg/reader.go:146: return UnsupportedError("downsample ratio")
On 2009/12/07 23:40:23, r wrote:
> ditto

Done.

http://codereview.appspot.com/164056/diff/2002/2007#newcode209
src/pkg/image/jpeg/reader.go:209: d.image.Pixel[py][px] =
image.RGBAColor{uint8(r), uint8(g), uint8(b), 0xff};
On 2009/12/07 23:40:23, r wrote:
> this won't be the fastest code out there but it's fine for now

Were you referring to just the d.image.Pixel assignment or the whole calcPixel
method?

http://codereview.appspot.com/164056/diff/2002/2007#newcode323
src/pkg/image/jpeg/reader.go:323: idct(d.blocks[i][j][0:dctSize2]);
On 2009/12/07 23:40:23, r wrote:
> see comment in  idct.go

Done.

http://codereview.appspot.com/164056/diff/2002/2007#newcode354
src/pkg/image/jpeg/reader.go:354: if err != nil {
On 2009/12/07 23:40:23, r wrote:
> fold lines together

See line 105.

http://codereview.appspot.com/164056/diff/2002/2007#newcode358
src/pkg/image/jpeg/reader.go:358: return nil, FormatError("not a JPEG file")
On 2009/12/07 23:40:23, r wrote:
> again, same error two places

Done.

[r, 2009-12-14 02:29:39]

http://codereview.appspot.com/164056/diff/3007/2015
File src/pkg/image/jpeg/idct.go (right):

http://codereview.appspot.com/164056/diff/3007/2015#newcode187
src/pkg/image/jpeg/idct.go:187: for i := 0; i < blockSize; i++ {
for i := range *b {

http://codereview.appspot.com/164056/diff/3007/2016
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/3007/2016#newcode167
src/pkg/image/jpeg/reader.go:167: for i := 0; i < blockSize; i++ {
for i := range d.quant[tq] maybe

http://codereview.appspot.com/164056/diff/3007/2016#newcode275
src/pkg/image/jpeg/reader.go:275: for k := 0; k < blockSize; k++ {
you could range over the block to avoid some indirects. worth picking off the
first two indices too.  or just have a pre-zeroed block and do d.blocks[i][j] =
allZeros. remember arrays are values.

[nigeltao, 2009-12-16 12:18:47]

Sync'ed and uploaded. The diff might look large because there's no more
semi-colons, but nothing's changed apart from the three straightforward "Done"s.

http://codereview.appspot.com/164056/diff/3007/2015
File src/pkg/image/jpeg/idct.go (right):

http://codereview.appspot.com/164056/diff/3007/2015#newcode187
src/pkg/image/jpeg/idct.go:187: for i := 0; i < blockSize; i++ {
On 2009/12/14 02:29:39, r wrote:
> for i := range *b {

Done.

http://codereview.appspot.com/164056/diff/3007/2016
File src/pkg/image/jpeg/reader.go (right):

http://codereview.appspot.com/164056/diff/3007/2016#newcode167
src/pkg/image/jpeg/reader.go:167: for i := 0; i < blockSize; i++ {
On 2009/12/14 02:29:39, r wrote:
> for i := range d.quant[tq] maybe

Done.

http://codereview.appspot.com/164056/diff/3007/2016#newcode275
src/pkg/image/jpeg/reader.go:275: for k := 0; k < blockSize; k++ {
On 2009/12/14 02:29:39, r wrote:
> you could range over the block to avoid some indirects. worth picking off the
> first two indices too.  or just have a pre-zeroed block and do d.blocks[i][j]
=
> allZeros. remember arrays are values.

Done.

[r, 2009-12-16 22:19:17]

LGTM

[nigeltao, 2009-12-16 23:35:04]

*** Submitted as http://code.google.com/p/go/source/detail?r=5b81b7a58de1 ***

Basic image/jpeg decoder.

This is not a complete JPEG implementation (e.g. it does not handle
progressive JPEGs or restart markers), but I was able to take a photo
with my phone, and view the resultant JPEG in pure Go.

The decoder is simple, but slow. The Huffman decoder in particular
should be easily improvable, but optimization is left to future
changelists. Being able to inline functions in the inner loop should
also help performance.

The output is not pixel-for-pixel identical to libjpeg, although
identical behavior isn't necessarily a goal, since JPEG is a lossy
codec. There are at least two reasons for the discrepancy.

First, the inverse DCT algorithm used is the same as Plan9's
src/cmd/jpg, which has different rounding errors from libjpeg's
default IDCT implementation. Note that libjpeg actually has three
different IDCT implementations: one floating point, and two fixed
point. Out of those four, Plan9's seemed the simplest to understand,
partly because it has no #ifdef's or C macros.

Second, for 4:2:2 or 4:2:0 chroma sampling, this implementation does
nearest neighbor upsampling, compared to libjpeg's triangle filter
(e.g. see h2v1_fancy_upsample in jdsample.c).

The difference from the first reason is typically zero, but sometimes
1 (out of 256) in YCbCr space, or double that in RGB space. The
difference from the second reason can be as large as 8/256 in YCbCr
space, in regions of steep chroma gradients. Informal eyeballing
suggests that the net difference is typically imperceptible, though.

R=r
CC=golang-dev, rsc
http://codereview.appspot.com/164056