dct_test.go

     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  	"fmt"
     9  	"math"
    10  	"math/rand"
    11  	"strings"
    12  	"testing"
    13  )
    14  
    15  func benchmarkDCT(b *testing.B, f func(*block)) {
    16  	b.StopTimer()
    17  	blocks := make([]block, 0, b.N*len(testBlocks))
    18  	for i := 0; i < b.N; i++ {
    19  		blocks = append(blocks, testBlocks[:]...)
    20  	}
    21  	b.StartTimer()
    22  	for i := range blocks {
    23  		f(&blocks[i])
    24  	}
    25  }
    26  
    27  func BenchmarkFDCT(b *testing.B) {
    28  	benchmarkDCT(b, fdct)
    29  }
    30  
    31  func BenchmarkIDCT(b *testing.B) {
    32  	benchmarkDCT(b, idct)
    33  }
    34  
    35  func TestDCT(t *testing.T) {
    36  	blocks := make([]block, len(testBlocks))
    37  	copy(blocks, testBlocks[:])
    38  
    39  	// Append some randomly generated blocks of varying sparseness.
    40  	r := rand.New(rand.NewSource(123))
    41  	for i := 0; i < 100; i++ {
    42  		b := block{}
    43  		n := r.Int() % 64
    44  		for j := 0; j < n; j++ {
    45  			b[r.Int()%len(b)] = r.Int31() % 256
    46  		}
    47  		blocks = append(blocks, b)
    48  	}
    49  
    50  	// Check that the FDCT and IDCT functions are inverses, after a scale and
    51  	// level shift. Scaling reduces the rounding errors in the conversion from
    52  	// floats to ints.
    53  	for i, b := range blocks {
    54  		got, want := b, b
    55  		for j := range got {
    56  			got[j] = (got[j] - 128) * 8
    57  		}
    58  		slowFDCT(&got)
    59  		slowIDCT(&got)
    60  		for j := range got {
    61  			got[j] = got[j]/8 + 128
    62  		}
    63  		if differ(&got, &want) {
    64  			t.Errorf("i=%d: IDCT(FDCT)\nsrc\n%s\ngot\n%s\nwant\n%s\n", i, &b, &got, &want)
    65  		}
    66  	}
    67  
    68  	// Check that the optimized and slow FDCT implementations agree.
    69  	// The fdct function already does a scale and level shift.
    70  	for i, b := range blocks {
    71  		got, want := b, b
    72  		fdct(&got)
    73  		for j := range want {
    74  			want[j] = (want[j] - 128) * 8
    75  		}
    76  		slowFDCT(&want)
    77  		if differ(&got, &want) {
    78  			t.Errorf("i=%d: FDCT\nsrc\n%s\ngot\n%s\nwant\n%s\n", i, &b, &got, &want)
    79  		}
    80  	}
    81  
    82  	// Check that the optimized and slow IDCT implementations agree.
    83  	for i, b := range blocks {
    84  		got, want := b, b
    85  		idct(&got)
    86  		slowIDCT(&want)
    87  		if differ(&got, &want) {
    88  			t.Errorf("i=%d: IDCT\nsrc\n%s\ngot\n%s\nwant\n%s\n", i, &b, &got, &want)
    89  		}
    90  	}
    91  }
    92  
    93  // differ reports whether any pair-wise elements in b0 and b1 differ by 2 or
    94  // more. That tolerance is because there isn't a single definitive decoding of
    95  // a given JPEG image, even before the YCbCr to RGB conversion; implementations
    96  // can have different IDCT rounding errors.
    97  func differ(b0, b1 *block) bool {
    98  	for i := range b0 {
    99  		delta := b0[i] - b1[i]
   100  		if delta < -2 || +2 < delta {
   101  			return true
   102  		}
   103  	}
   104  	return false
   105  }
   106  
   107  // alpha returns 1 if i is 0 and returns √2 otherwise.
   108  func alpha(i int) float64 {
   109  	if i == 0 {
   110  		return 1
   111  	}
   112  	return math.Sqrt2
   113  }
   114  
   115  var cosines = [32]float64{
   116  	+1.0000000000000000000000000000000000000000000000000000000000000000, // cos(π/16 *  0)
   117  	+0.9807852804032304491261822361342390369739337308933360950029160885, // cos(π/16 *  1)
   118  	+0.9238795325112867561281831893967882868224166258636424861150977312, // cos(π/16 *  2)
   119  	+0.8314696123025452370787883776179057567385608119872499634461245902, // cos(π/16 *  3)
   120  	+0.7071067811865475244008443621048490392848359376884740365883398689, // cos(π/16 *  4)
   121  	+0.5555702330196022247428308139485328743749371907548040459241535282, // cos(π/16 *  5)
   122  	+0.3826834323650897717284599840303988667613445624856270414338006356, // cos(π/16 *  6)
   123  	+0.1950903220161282678482848684770222409276916177519548077545020894, // cos(π/16 *  7)
   124  
   125  	-0.0000000000000000000000000000000000000000000000000000000000000000, // cos(π/16 *  8)
   126  	-0.1950903220161282678482848684770222409276916177519548077545020894, // cos(π/16 *  9)
   127  	-0.3826834323650897717284599840303988667613445624856270414338006356, // cos(π/16 * 10)
   128  	-0.5555702330196022247428308139485328743749371907548040459241535282, // cos(π/16 * 11)
   129  	-0.7071067811865475244008443621048490392848359376884740365883398689, // cos(π/16 * 12)
   130  	-0.8314696123025452370787883776179057567385608119872499634461245902, // cos(π/16 * 13)
   131  	-0.9238795325112867561281831893967882868224166258636424861150977312, // cos(π/16 * 14)
   132  	-0.9807852804032304491261822361342390369739337308933360950029160885, // cos(π/16 * 15)
   133  
   134  	-1.0000000000000000000000000000000000000000000000000000000000000000, // cos(π/16 * 16)
   135  	-0.9807852804032304491261822361342390369739337308933360950029160885, // cos(π/16 * 17)
   136  	-0.9238795325112867561281831893967882868224166258636424861150977312, // cos(π/16 * 18)
   137  	-0.8314696123025452370787883776179057567385608119872499634461245902, // cos(π/16 * 19)
   138  	-0.7071067811865475244008443621048490392848359376884740365883398689, // cos(π/16 * 20)
   139  	-0.5555702330196022247428308139485328743749371907548040459241535282, // cos(π/16 * 21)
   140  	-0.3826834323650897717284599840303988667613445624856270414338006356, // cos(π/16 * 22)
   141  	-0.1950903220161282678482848684770222409276916177519548077545020894, // cos(π/16 * 23)
   142  
   143  	+0.0000000000000000000000000000000000000000000000000000000000000000, // cos(π/16 * 24)
   144  	+0.1950903220161282678482848684770222409276916177519548077545020894, // cos(π/16 * 25)
   145  	+0.3826834323650897717284599840303988667613445624856270414338006356, // cos(π/16 * 26)
   146  	+0.5555702330196022247428308139485328743749371907548040459241535282, // cos(π/16 * 27)
   147  	+0.7071067811865475244008443621048490392848359376884740365883398689, // cos(π/16 * 28)
   148  	+0.8314696123025452370787883776179057567385608119872499634461245902, // cos(π/16 * 29)
   149  	+0.9238795325112867561281831893967882868224166258636424861150977312, // cos(π/16 * 30)
   150  	+0.9807852804032304491261822361342390369739337308933360950029160885, // cos(π/16 * 31)
   151  }
   152  
   153  // slowFDCT performs the 8*8 2-dimensional forward discrete cosine transform:
   154  //
   155  //	dst[u,v] = (1/8) * Σ_x Σ_y alpha(u) * alpha(v) * src[x,y] *
   156  //		cos((π/2) * (2*x + 1) * u / 8) *
   157  //		cos((π/2) * (2*y + 1) * v / 8)
   158  //
   159  // x and y are in pixel space, and u and v are in transform space.
   160  //
   161  // b acts as both dst and src.
   162  func slowFDCT(b *block) {
   163  	var dst [blockSize]float64
   164  	for v := 0; v < 8; v++ {
   165  		for u := 0; u < 8; u++ {
   166  			sum := 0.0
   167  			for y := 0; y < 8; y++ {
   168  				for x := 0; x < 8; x++ {
   169  					sum += alpha(u) * alpha(v) * float64(b[8*y+x]) *
   170  						cosines[((2*x+1)*u)%32] *
   171  						cosines[((2*y+1)*v)%32]
   172  				}
   173  			}
   174  			dst[8*v+u] = sum / 8
   175  		}
   176  	}
   177  	// Convert from float64 to int32.
   178  	for i := range dst {
   179  		b[i] = int32(dst[i] + 0.5)
   180  	}
   181  }
   182  
   183  // slowIDCT performs the 8*8 2-dimensional inverse discrete cosine transform:
   184  //
   185  //	dst[x,y] = (1/8) * Σ_u Σ_v alpha(u) * alpha(v) * src[u,v] *
   186  //		cos((π/2) * (2*x + 1) * u / 8) *
   187  //		cos((π/2) * (2*y + 1) * v / 8)
   188  //
   189  // x and y are in pixel space, and u and v are in transform space.
   190  //
   191  // b acts as both dst and src.
   192  func slowIDCT(b *block) {
   193  	var dst [blockSize]float64
   194  	for y := 0; y < 8; y++ {
   195  		for x := 0; x < 8; x++ {
   196  			sum := 0.0
   197  			for v := 0; v < 8; v++ {
   198  				for u := 0; u < 8; u++ {
   199  					sum += alpha(u) * alpha(v) * float64(b[8*v+u]) *
   200  						cosines[((2*x+1)*u)%32] *
   201  						cosines[((2*y+1)*v)%32]
   202  				}
   203  			}
   204  			dst[8*y+x] = sum / 8
   205  		}
   206  	}
   207  	// Convert from float64 to int32.
   208  	for i := range dst {
   209  		b[i] = int32(dst[i] + 0.5)
   210  	}
   211  }
   212  
   213  func (b *block) String() string {
   214  	s := &strings.Builder{}
   215  	fmt.Fprintf(s, "{\n")
   216  	for y := 0; y < 8; y++ {
   217  		fmt.Fprintf(s, "\t")
   218  		for x := 0; x < 8; x++ {
   219  			fmt.Fprintf(s, "0x%04x, ", uint16(b[8*y+x]))
   220  		}
   221  		fmt.Fprintln(s)
   222  	}
   223  	fmt.Fprintf(s, "}")
   224  	return s.String()
   225  }
   226  
   227  // testBlocks are the first 10 pre-IDCT blocks from ../testdata/video-001.jpeg.
   228  var testBlocks = [10]block{
   229  	{
   230  		0x7f, 0xf6, 0x01, 0x07, 0xff, 0x00, 0x00, 0x00,
   231  		0xf5, 0x01, 0xfa, 0x01, 0xfe, 0x00, 0x01, 0x00,
   232  		0x05, 0x05, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00,
   233  		0x01, 0xff, 0xf8, 0x00, 0x01, 0xff, 0x00, 0x00,
   234  		0x00, 0x01, 0x00, 0x01, 0x00, 0xff, 0xff, 0x00,
   235  		0xff, 0x0c, 0x00, 0x00, 0x00, 0x00, 0xff, 0x01,
   236  		0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
   237  		0x01, 0x00, 0x00, 0x01, 0xff, 0x01, 0x00, 0xfe,
   238  	},
   239  	{
   240  		0x29, 0x07, 0x00, 0xfc, 0x01, 0x01, 0x00, 0x00,
   241  		0x07, 0x00, 0x03, 0x00, 0x01, 0x00, 0xff, 0xff,
   242  		0xff, 0xfd, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
   243  		0x00, 0x00, 0x04, 0x00, 0xff, 0x01, 0x00, 0x00,
   244  		0x01, 0x00, 0x01, 0xff, 0x00, 0x00, 0x00, 0x00,
   245  		0x01, 0xfa, 0x01, 0x00, 0x01, 0x00, 0x01, 0xff,
   246  		0x00, 0x00, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
   247  		0x00, 0x00, 0x00, 0xff, 0x00, 0xff, 0x00, 0x02,
   248  	},
   249  	{
   250  		0xc5, 0xfa, 0x01, 0x00, 0x00, 0x01, 0x00, 0xff,
   251  		0x02, 0xff, 0x01, 0x00, 0x01, 0x00, 0xff, 0x00,
   252  		0xff, 0xff, 0x00, 0xff, 0x01, 0x00, 0x00, 0x00,
   253  		0xff, 0x00, 0x01, 0x00, 0x00, 0x00, 0xff, 0x00,
   254  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff,
   255  		0x00, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   256  		0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   257  		0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   258  	},
   259  	{
   260  		0x86, 0x05, 0x00, 0x02, 0x00, 0x00, 0x01, 0x00,
   261  		0xf2, 0x06, 0x00, 0x00, 0x01, 0x02, 0x00, 0x00,
   262  		0xf6, 0xfa, 0xf9, 0x00, 0xff, 0x01, 0x00, 0x00,
   263  		0xf9, 0x00, 0x00, 0xff, 0x00, 0x00, 0x00, 0x00,
   264  		0x00, 0xff, 0x00, 0xff, 0xff, 0xff, 0x00, 0x00,
   265  		0xff, 0x00, 0x00, 0x01, 0x00, 0xff, 0x01, 0x00,
   266  		0x00, 0x00, 0x00, 0xff, 0x00, 0x00, 0x00, 0x01,
   267  		0x00, 0x01, 0xff, 0x01, 0x00, 0xff, 0x00, 0x00,
   268  	},
   269  	{
   270  		0x24, 0xfe, 0x00, 0xff, 0x00, 0xff, 0xff, 0x00,
   271  		0x08, 0xfd, 0x00, 0x01, 0x01, 0x00, 0x01, 0x00,
   272  		0x06, 0x03, 0x03, 0xff, 0x00, 0x00, 0x00, 0x00,
   273  		0x04, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff,
   274  		0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01,
   275  		0x01, 0x00, 0x01, 0xff, 0x00, 0x01, 0x00, 0x00,
   276  		0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   277  		0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0xff, 0x01,
   278  	},
   279  	{
   280  		0xcd, 0xff, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01,
   281  		0x03, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff,
   282  		0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00,
   283  		0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   284  		0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x00,
   285  		0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
   286  		0x00, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   287  		0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0xff,
   288  	},
   289  	{
   290  		0x81, 0xfe, 0x05, 0xff, 0x01, 0xff, 0x01, 0x00,
   291  		0xef, 0xf9, 0x00, 0xf9, 0x00, 0xff, 0x00, 0xff,
   292  		0x05, 0xf9, 0x00, 0xf8, 0x01, 0xff, 0x01, 0xff,
   293  		0x00, 0xff, 0x07, 0x00, 0x01, 0x00, 0x00, 0x00,
   294  		0x01, 0x00, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00,
   295  		0x01, 0x00, 0x00, 0x00, 0xff, 0xff, 0x00, 0x01,
   296  		0xff, 0x01, 0x01, 0x00, 0xff, 0x00, 0x00, 0x00,
   297  		0x01, 0x01, 0x00, 0xff, 0x00, 0x00, 0x00, 0xff,
   298  	},
   299  	{
   300  		0x28, 0x00, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00,
   301  		0x0b, 0x02, 0x01, 0x03, 0x00, 0xff, 0x00, 0x01,
   302  		0xfe, 0x02, 0x01, 0x03, 0xff, 0x00, 0x00, 0x00,
   303  		0x01, 0x00, 0xfd, 0x00, 0x01, 0x00, 0xff, 0x00,
   304  		0x01, 0xff, 0x00, 0xff, 0x01, 0x00, 0x00, 0x00,
   305  		0x00, 0x00, 0x00, 0xff, 0x01, 0x01, 0x00, 0xff,
   306  		0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   307  		0xff, 0xff, 0x00, 0x00, 0x00, 0xff, 0x00, 0x01,
   308  	},
   309  	{
   310  		0xdf, 0xf9, 0xfe, 0x00, 0x03, 0x01, 0xff, 0xff,
   311  		0x04, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
   312  		0xff, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x01,
   313  		0x00, 0x00, 0xfe, 0x01, 0x00, 0x00, 0x00, 0x00,
   314  		0x00, 0x00, 0xff, 0x01, 0x00, 0x00, 0x00, 0x01,
   315  		0xff, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00,
   316  		0x00, 0xff, 0x00, 0xff, 0x01, 0x00, 0x00, 0x01,
   317  		0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00,
   318  	},
   319  	{
   320  		0x88, 0xfd, 0x00, 0x00, 0xff, 0x00, 0x01, 0xff,
   321  		0xe1, 0x06, 0x06, 0x01, 0xff, 0x00, 0x01, 0x00,
   322  		0x08, 0x00, 0xfa, 0x00, 0xff, 0xff, 0xff, 0xff,
   323  		0x08, 0x01, 0x00, 0xff, 0x01, 0xff, 0x00, 0x00,
   324  		0xf5, 0xff, 0x00, 0x01, 0xff, 0x01, 0x01, 0x00,
   325  		0xff, 0xff, 0x01, 0xff, 0x01, 0x00, 0x01, 0x00,
   326  		0x00, 0x01, 0x01, 0xff, 0x00, 0xff, 0x00, 0x01,
   327  		0x02, 0x00, 0x00, 0xff, 0xff, 0x00, 0xff, 0x00,
   328  	},
   329  }
   330
View as plain text