From 1423ecb1266c9af288caa2723988a326adf7118e Mon Sep 17 00:00:00 2001 From: Nigel Tao Date: Fri, 25 May 2012 14:08:51 +1000 Subject: [PATCH] image/png: optimize the paeth filter implementation. image/png benchmarks: benchmark old ns/op new ns/op delta BenchmarkPaeth 10 7 -29.21% BenchmarkDecodeGray 2381745 2241620 -5.88% BenchmarkDecodeNRGBAGradient 9535555 8835100 -7.35% BenchmarkDecodeNRGBAOpaque 8189590 7611865 -7.05% BenchmarkDecodePaletted 1300688 1301940 +0.10% BenchmarkDecodeRGB 6760146 6317082 -6.55% BenchmarkEncodePaletted 6048596 6122666 +1.22% BenchmarkEncodeRGBOpaque 18891140 19474230 +3.09% BenchmarkEncodeRGBA 78945350 78552600 -0.50% Wall time for Denis Cheremisov's PNG-decoding program given in https://groups.google.com/group/golang-nuts/browse_thread/thread/22aa8a05040fdd49 Before: 2.25s After: 2.27s Delta: +1% The same program, but with a different PNG input file (http://upload.wikimedia.org/wikipedia/commons/4/47/PNG_transparency_demonstration_1.png) and only 100 iterations instead of 1000 Before: 4.78s After: 4.42s Delta: -8% R=rsc CC=golang-dev https://golang.org/cl/6242056 --- src/pkg/image/png/paeth_test.go | 51 +++++++++++++++++++++++++++++++++ src/pkg/image/png/reader.go | 33 +++++++++++++-------- 2 files changed, 72 insertions(+), 12 deletions(-) create mode 100644 src/pkg/image/png/paeth_test.go diff --git a/src/pkg/image/png/paeth_test.go b/src/pkg/image/png/paeth_test.go new file mode 100644 index 0000000000..b0cec1c8f6 --- /dev/null +++ b/src/pkg/image/png/paeth_test.go @@ -0,0 +1,51 @@ +// 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 png + +import ( + "testing" +) + +func abs(x int) int { + if x < 0 { + return -x + } + return x +} + +// slowPaeth is a slow but simple implementation of the Paeth function. +// It is a straight port of the sample code in the PNG spec, section 9.4. +func slowPaeth(a, b, c uint8) uint8 { + p := int(a) + int(b) - int(c) + pa := abs(p - int(a)) + pb := abs(p - int(b)) + pc := abs(p - int(c)) + if pa <= pb && pa <= pc { + return a + } else if pb <= pc { + return b + } + return c +} + +func TestPaeth(t *testing.T) { + for a := 0; a < 256; a += 15 { + for b := 0; b < 256; b += 15 { + for c := 0; c < 256; c += 15 { + got := paeth(uint8(a), uint8(b), uint8(c)) + want := slowPaeth(uint8(a), uint8(b), uint8(c)) + if got != want { + t.Errorf("a, b, c = %d, %d, %d: got %d, want %d", a, b, c, got, want) + } + } + } + } +} + +func BenchmarkPaeth(b *testing.B) { + for i := 0; i < b.N; i++ { + paeth(uint8(i>>16), uint8(i>>8), uint8(i)) + } +} diff --git a/src/pkg/image/png/reader.go b/src/pkg/image/png/reader.go index c781be1837..6b2100badd 100644 --- a/src/pkg/image/png/reader.go +++ b/src/pkg/image/png/reader.go @@ -98,13 +98,6 @@ type UnsupportedError string func (e UnsupportedError) Error() string { return "png: unsupported feature: " + string(e) } -func abs(x int) int { - if x < 0 { - return -x - } - return x -} - func min(a, b int) int { if a < b { return a @@ -241,12 +234,28 @@ func (d *decoder) parsetRNS(length uint32) error { return d.verifyChecksum() } -// The Paeth filter function, as per the PNG specification. +// paeth implements the Paeth filter function, as per the PNG specification. func paeth(a, b, c uint8) uint8 { - p := int(a) + int(b) - int(c) - pa := abs(p - int(a)) - pb := abs(p - int(b)) - pc := abs(p - int(c)) + // This is an optimized version of the sample code in the PNG spec. + // For example, the sample code starts with: + // p := int(a) + int(b) - int(c) + // pa := abs(p - int(a)) + // but the optimized form uses fewer arithmetic operations: + // pa := int(b) - int(c) + // pa = abs(pa) + pc := int(c) + pa := int(b) - pc + pb := int(a) - pc + pc = pa + pb + if pa < 0 { + pa = -pa + } + if pb < 0 { + pb = -pb + } + if pc < 0 { + pc = -pc + } if pa <= pb && pa <= pc { return a } else if pb <= pc { -- 2.48.1