Source file
src/image/jpeg/dct_test.go
1
2
3
4
5 package jpeg
6
7 import (
8 "fmt"
9 "math"
10 "math/big"
11 "math/rand"
12 "strings"
13 "testing"
14 )
15
16 func benchmarkDCT(b *testing.B, f func(*block)) {
17 var blk block
18 for b.Loop() {
19 for _, blk = range testBlocks {
20 f(&blk)
21 }
22 }
23 }
24
25 func BenchmarkFDCT(b *testing.B) {
26 benchmarkDCT(b, fdct)
27 }
28
29 func BenchmarkIDCT(b *testing.B) {
30 benchmarkDCT(b, idct)
31 }
32
33 const testSlowVsBig = true
34
35 func TestDCT(t *testing.T) {
36 blocks := make([]block, len(testBlocks))
37 copy(blocks, testBlocks[:])
38
39
40 blocks = append(blocks, block{})
41
42
43 for i := range blockSize {
44 var b block
45 b[i] = 255
46 blocks = append(blocks, b)
47 }
48
49
50 var ones block
51 for i := range ones {
52 ones[i] = 255
53 }
54 blocks = append(blocks, ones)
55
56
57 for i := range blockSize {
58 ones[i] = 0
59 blocks = append(blocks, ones)
60 ones[i] = 255
61 }
62
63
64 r := rand.New(rand.NewSource(123))
65 for i := 0; i < 100; i++ {
66 b := block{}
67 n := r.Int() % 64
68 for j := 0; j < n; j++ {
69 b[r.Int()%len(b)] = r.Int31() % 256
70 }
71 blocks = append(blocks, b)
72 }
73
74
75
76
77
78
79 slowRoundTrip := func(b *block) {
80 slowFDCT(b)
81 slowIDCT(b)
82 for j := range b {
83 b[j] = b[j]/8 + 128
84 }
85 }
86 nop := func(*block) {}
87 testDCT(t, "IDCT(FDCT)", blocks, slowRoundTrip, nop, 1, 8)
88
89 if testSlowVsBig {
90 testDCT(t, "slowFDCT", blocks, slowFDCT, slowerFDCT, 0, 64)
91 testDCT(t, "slowIDCT", blocks, slowIDCT, slowerIDCT, 0, 64)
92 }
93
94
95 testDCT(t, "FDCT", blocks, fdct, slowFDCT, 1, 8)
96 testDCT(t, "IDCT", blocks, idct, slowIDCT, 1, 8)
97 }
98
99 func testDCT(t *testing.T, name string, blocks []block, fhave, fwant func(*block), tolerance int32, maxCloseCalls int) {
100 t.Run(name, func(t *testing.T) {
101 totalClose := 0
102 for i, b := range blocks {
103 have, want := b, b
104 fhave(&have)
105 fwant(&want)
106 d, n := differ(&have, &want, tolerance)
107 if d >= 0 || n > maxCloseCalls {
108 fail := ""
109 if d >= 0 {
110 fail = fmt.Sprintf("diff at %d,%d", d/8, d%8)
111 }
112 if n > maxCloseCalls {
113 if fail != "" {
114 fail += "; "
115 }
116 fail += fmt.Sprintf("%d close calls", n)
117 }
118 t.Errorf("i=%d: %s (%s)\nsrc\n%s\nhave\n%s\nwant\n%s\n",
119 i, name, fail, &b, &have, &want)
120 }
121 totalClose += n
122 }
123 if tolerance > 0 {
124 t.Logf("%d/%d total close calls", totalClose, len(blocks)*blockSize)
125 }
126 })
127 }
128
129
130
131
132
133
134
135
136
137
138 func differ(b0, b1 *block, ok int32) (index, closeCalls int) {
139 index = -1
140 for i := range b0 {
141 delta := b0[i] - b1[i]
142 if delta < -ok || ok < delta {
143 if index < 0 {
144 index = i
145 }
146 }
147 if delta <= -ok || ok <= delta {
148 closeCalls++
149 }
150 }
151 return
152 }
153
154
155 func alpha(i int) float64 {
156 if i == 0 {
157 return 1
158 }
159 return math.Sqrt2
160 }
161
162
163 func bigAlpha(i int) *big.Float {
164 if i == 0 {
165 return bigFloat1
166 }
167 return bigFloatSqrt2
168 }
169
170 var cosines = [32]float64{
171 +1.0000000000000000000000000000000000000000000000000000000000000000,
172 +0.9807852804032304491261822361342390369739337308933360950029160885,
173 +0.9238795325112867561281831893967882868224166258636424861150977312,
174 +0.8314696123025452370787883776179057567385608119872499634461245902,
175 +0.7071067811865475244008443621048490392848359376884740365883398689,
176 +0.5555702330196022247428308139485328743749371907548040459241535282,
177 +0.3826834323650897717284599840303988667613445624856270414338006356,
178 +0.1950903220161282678482848684770222409276916177519548077545020894,
179
180 -0.0000000000000000000000000000000000000000000000000000000000000000,
181 -0.1950903220161282678482848684770222409276916177519548077545020894,
182 -0.3826834323650897717284599840303988667613445624856270414338006356,
183 -0.5555702330196022247428308139485328743749371907548040459241535282,
184 -0.7071067811865475244008443621048490392848359376884740365883398689,
185 -0.8314696123025452370787883776179057567385608119872499634461245902,
186 -0.9238795325112867561281831893967882868224166258636424861150977312,
187 -0.9807852804032304491261822361342390369739337308933360950029160885,
188
189 -1.0000000000000000000000000000000000000000000000000000000000000000,
190 -0.9807852804032304491261822361342390369739337308933360950029160885,
191 -0.9238795325112867561281831893967882868224166258636424861150977312,
192 -0.8314696123025452370787883776179057567385608119872499634461245902,
193 -0.7071067811865475244008443621048490392848359376884740365883398689,
194 -0.5555702330196022247428308139485328743749371907548040459241535282,
195 -0.3826834323650897717284599840303988667613445624856270414338006356,
196 -0.1950903220161282678482848684770222409276916177519548077545020894,
197
198 +0.0000000000000000000000000000000000000000000000000000000000000000,
199 +0.1950903220161282678482848684770222409276916177519548077545020894,
200 +0.3826834323650897717284599840303988667613445624856270414338006356,
201 +0.5555702330196022247428308139485328743749371907548040459241535282,
202 +0.7071067811865475244008443621048490392848359376884740365883398689,
203 +0.8314696123025452370787883776179057567385608119872499634461245902,
204 +0.9238795325112867561281831893967882868224166258636424861150977312,
205 +0.9807852804032304491261822361342390369739337308933360950029160885,
206 }
207
208 func bigFloat(s string) *big.Float {
209 f, ok := new(big.Float).SetString(s)
210 if !ok {
211 panic("bad float")
212 }
213 return f
214 }
215
216 var (
217 bigFloat1 = big.NewFloat(1)
218 bigFloatSqrt2 = bigFloat("1.41421356237309504880168872420969807856967187537694807317667974")
219 )
220
221 var bigCosines = [32]*big.Float{
222 bigFloat("+1.0000000000000000000000000000000000000000000000000000000000000000"),
223 bigFloat("+0.9807852804032304491261822361342390369739337308933360950029160885"),
224 bigFloat("+0.9238795325112867561281831893967882868224166258636424861150977312"),
225 bigFloat("+0.8314696123025452370787883776179057567385608119872499634461245902"),
226 bigFloat("+0.7071067811865475244008443621048490392848359376884740365883398689"),
227 bigFloat("+0.5555702330196022247428308139485328743749371907548040459241535282"),
228 bigFloat("+0.3826834323650897717284599840303988667613445624856270414338006356"),
229 bigFloat("+0.1950903220161282678482848684770222409276916177519548077545020894"),
230
231 bigFloat("-0.0000000000000000000000000000000000000000000000000000000000000000"),
232 bigFloat("-0.1950903220161282678482848684770222409276916177519548077545020894"),
233 bigFloat("-0.3826834323650897717284599840303988667613445624856270414338006356"),
234 bigFloat("-0.5555702330196022247428308139485328743749371907548040459241535282"),
235 bigFloat("-0.7071067811865475244008443621048490392848359376884740365883398689"),
236 bigFloat("-0.8314696123025452370787883776179057567385608119872499634461245902"),
237 bigFloat("-0.9238795325112867561281831893967882868224166258636424861150977312"),
238 bigFloat("-0.9807852804032304491261822361342390369739337308933360950029160885"),
239
240 bigFloat("-1.0000000000000000000000000000000000000000000000000000000000000000"),
241 bigFloat("-0.9807852804032304491261822361342390369739337308933360950029160885"),
242 bigFloat("-0.9238795325112867561281831893967882868224166258636424861150977312"),
243 bigFloat("-0.8314696123025452370787883776179057567385608119872499634461245902"),
244 bigFloat("-0.7071067811865475244008443621048490392848359376884740365883398689"),
245 bigFloat("-0.5555702330196022247428308139485328743749371907548040459241535282"),
246 bigFloat("-0.3826834323650897717284599840303988667613445624856270414338006356"),
247 bigFloat("-0.1950903220161282678482848684770222409276916177519548077545020894"),
248
249 bigFloat("+0.0000000000000000000000000000000000000000000000000000000000000000"),
250 bigFloat("+0.1950903220161282678482848684770222409276916177519548077545020894"),
251 bigFloat("+0.3826834323650897717284599840303988667613445624856270414338006356"),
252 bigFloat("+0.5555702330196022247428308139485328743749371907548040459241535282"),
253 bigFloat("+0.7071067811865475244008443621048490392848359376884740365883398689"),
254 bigFloat("+0.8314696123025452370787883776179057567385608119872499634461245902"),
255 bigFloat("+0.9238795325112867561281831893967882868224166258636424861150977312"),
256 bigFloat("+0.9807852804032304491261822361342390369739337308933360950029160885"),
257 }
258
259
260
261
262
263
264
265
266
267
268 func slowFDCT(b *block) {
269 var dst block
270 for v := 0; v < 8; v++ {
271 for u := 0; u < 8; u++ {
272 sum := 0.0
273 for y := 0; y < 8; y++ {
274 for x := 0; x < 8; x++ {
275 sum += alpha(u) * alpha(v) * float64(b[8*y+x]-128) *
276 cosines[((2*x+1)*u)%32] *
277 cosines[((2*y+1)*v)%32]
278 }
279 }
280 dst[8*v+u] = int32(math.Round(sum))
281 }
282 }
283 *b = dst
284 }
285
286
287 func slowerFDCT(b *block) {
288 var dst block
289 for v := 0; v < 8; v++ {
290 for u := 0; u < 8; u++ {
291 sum := big.NewFloat(0)
292 for y := 0; y < 8; y++ {
293 for x := 0; x < 8; x++ {
294 f := big.NewFloat(float64(b[8*y+x] - 128))
295 f = new(big.Float).Mul(f, bigAlpha(u))
296 f = new(big.Float).Mul(f, bigAlpha(v))
297 f = new(big.Float).Mul(f, bigCosines[((2*x+1)*u)%32])
298 f = new(big.Float).Mul(f, bigCosines[((2*y+1)*v)%32])
299 sum = new(big.Float).Add(sum, f)
300 }
301 }
302
303
304 if sum.Sign() > 0 {
305 sum = new(big.Float).Add(sum, big.NewFloat(+0.5))
306 } else {
307 sum = new(big.Float).Add(sum, big.NewFloat(-0.5))
308 }
309 i, _ := sum.Int64()
310 dst[8*v+u] = int32(i)
311 }
312 }
313 *b = dst
314 }
315
316
317
318
319
320
321
322
323
324
325 func slowIDCT(b *block) {
326 var dst block
327 for y := 0; y < 8; y++ {
328 for x := 0; x < 8; x++ {
329 sum := 0.0
330 for v := 0; v < 8; v++ {
331 for u := 0; u < 8; u++ {
332 sum += alpha(u) * alpha(v) * float64(b[8*v+u]) *
333 cosines[((2*x+1)*u)%32] *
334 cosines[((2*y+1)*v)%32]
335 }
336 }
337 dst[8*y+x] = int32(math.Round(sum / 8))
338 }
339 }
340 *b = dst
341 }
342
343
344 func slowerIDCT(b *block) {
345 var dst block
346 for y := 0; y < 8; y++ {
347 for x := 0; x < 8; x++ {
348 sum := big.NewFloat(0)
349 for v := 0; v < 8; v++ {
350 for u := 0; u < 8; u++ {
351 f := big.NewFloat(float64(b[8*v+u]))
352 f = new(big.Float).Mul(f, bigAlpha(u))
353 f = new(big.Float).Mul(f, bigAlpha(v))
354 f = new(big.Float).Mul(f, bigCosines[((2*x+1)*u)%32])
355 f = new(big.Float).Mul(f, bigCosines[((2*y+1)*v)%32])
356 f = new(big.Float).Quo(f, big.NewFloat(8))
357 sum = new(big.Float).Add(sum, f)
358 }
359 }
360
361
362 if sum.Sign() > 0 {
363 sum = new(big.Float).Add(sum, big.NewFloat(+0.5))
364 } else {
365 sum = new(big.Float).Add(sum, big.NewFloat(-0.5))
366 }
367 i, _ := sum.Int64()
368 dst[8*y+x] = int32(i)
369 }
370 }
371 *b = dst
372 }
373
374 func (b *block) String() string {
375 s := &strings.Builder{}
376 fmt.Fprintf(s, "{\n")
377 for y := 0; y < 8; y++ {
378 fmt.Fprintf(s, "\t")
379 for x := 0; x < 8; x++ {
380 fmt.Fprintf(s, "0x%04x, ", uint16(b[8*y+x]))
381 }
382 fmt.Fprintln(s)
383 }
384 fmt.Fprintf(s, "}")
385 return s.String()
386 }
387
388
389 var testBlocks = [10]block{
390 {
391 0x7f, 0xf6, 0x01, 0x07, 0xff, 0x00, 0x00, 0x00,
392 0xf5, 0x01, 0xfa, 0x01, 0xfe, 0x00, 0x01, 0x00,
393 0x05, 0x05, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00,
394 0x01, 0xff, 0xf8, 0x00, 0x01, 0xff, 0x00, 0x00,
395 0x00, 0x01, 0x00, 0x01, 0x00, 0xff, 0xff, 0x00,
396 0xff, 0x0c, 0x00, 0x00, 0x00, 0x00, 0xff, 0x01,
397 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
398 0x01, 0x00, 0x00, 0x01, 0xff, 0x01, 0x00, 0xfe,
399 },
400 {
401 0x29, 0x07, 0x00, 0xfc, 0x01, 0x01, 0x00, 0x00,
402 0x07, 0x00, 0x03, 0x00, 0x01, 0x00, 0xff, 0xff,
403 0xff, 0xfd, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
404 0x00, 0x00, 0x04, 0x00, 0xff, 0x01, 0x00, 0x00,
405 0x01, 0x00, 0x01, 0xff, 0x00, 0x00, 0x00, 0x00,
406 0x01, 0xfa, 0x01, 0x00, 0x01, 0x00, 0x01, 0xff,
407 0x00, 0x00, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
408 0x00, 0x00, 0x00, 0xff, 0x00, 0xff, 0x00, 0x02,
409 },
410 {
411 0xc5, 0xfa, 0x01, 0x00, 0x00, 0x01, 0x00, 0xff,
412 0x02, 0xff, 0x01, 0x00, 0x01, 0x00, 0xff, 0x00,
413 0xff, 0xff, 0x00, 0xff, 0x01, 0x00, 0x00, 0x00,
414 0xff, 0x00, 0x01, 0x00, 0x00, 0x00, 0xff, 0x00,
415 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff,
416 0x00, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
417 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
418 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
419 },
420 {
421 0x86, 0x05, 0x00, 0x02, 0x00, 0x00, 0x01, 0x00,
422 0xf2, 0x06, 0x00, 0x00, 0x01, 0x02, 0x00, 0x00,
423 0xf6, 0xfa, 0xf9, 0x00, 0xff, 0x01, 0x00, 0x00,
424 0xf9, 0x00, 0x00, 0xff, 0x00, 0x00, 0x00, 0x00,
425 0x00, 0xff, 0x00, 0xff, 0xff, 0xff, 0x00, 0x00,
426 0xff, 0x00, 0x00, 0x01, 0x00, 0xff, 0x01, 0x00,
427 0x00, 0x00, 0x00, 0xff, 0x00, 0x00, 0x00, 0x01,
428 0x00, 0x01, 0xff, 0x01, 0x00, 0xff, 0x00, 0x00,
429 },
430 {
431 0x24, 0xfe, 0x00, 0xff, 0x00, 0xff, 0xff, 0x00,
432 0x08, 0xfd, 0x00, 0x01, 0x01, 0x00, 0x01, 0x00,
433 0x06, 0x03, 0x03, 0xff, 0x00, 0x00, 0x00, 0x00,
434 0x04, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff,
435 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01,
436 0x01, 0x00, 0x01, 0xff, 0x00, 0x01, 0x00, 0x00,
437 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
438 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0xff, 0x01,
439 },
440 {
441 0xcd, 0xff, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01,
442 0x03, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff,
443 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00,
444 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
445 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x00,
446 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
447 0x00, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
448 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0xff,
449 },
450 {
451 0x81, 0xfe, 0x05, 0xff, 0x01, 0xff, 0x01, 0x00,
452 0xef, 0xf9, 0x00, 0xf9, 0x00, 0xff, 0x00, 0xff,
453 0x05, 0xf9, 0x00, 0xf8, 0x01, 0xff, 0x01, 0xff,
454 0x00, 0xff, 0x07, 0x00, 0x01, 0x00, 0x00, 0x00,
455 0x01, 0x00, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00,
456 0x01, 0x00, 0x00, 0x00, 0xff, 0xff, 0x00, 0x01,
457 0xff, 0x01, 0x01, 0x00, 0xff, 0x00, 0x00, 0x00,
458 0x01, 0x01, 0x00, 0xff, 0x00, 0x00, 0x00, 0xff,
459 },
460 {
461 0x28, 0x00, 0xfe, 0x00, 0x00, 0x00, 0x00, 0x00,
462 0x0b, 0x02, 0x01, 0x03, 0x00, 0xff, 0x00, 0x01,
463 0xfe, 0x02, 0x01, 0x03, 0xff, 0x00, 0x00, 0x00,
464 0x01, 0x00, 0xfd, 0x00, 0x01, 0x00, 0xff, 0x00,
465 0x01, 0xff, 0x00, 0xff, 0x01, 0x00, 0x00, 0x00,
466 0x00, 0x00, 0x00, 0xff, 0x01, 0x01, 0x00, 0xff,
467 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
468 0xff, 0xff, 0x00, 0x00, 0x00, 0xff, 0x00, 0x01,
469 },
470 {
471 0xdf, 0xf9, 0xfe, 0x00, 0x03, 0x01, 0xff, 0xff,
472 0x04, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00,
473 0xff, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x01,
474 0x00, 0x00, 0xfe, 0x01, 0x00, 0x00, 0x00, 0x00,
475 0x00, 0x00, 0xff, 0x01, 0x00, 0x00, 0x00, 0x01,
476 0xff, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00,
477 0x00, 0xff, 0x00, 0xff, 0x01, 0x00, 0x00, 0x01,
478 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00,
479 },
480 {
481 0x88, 0xfd, 0x00, 0x00, 0xff, 0x00, 0x01, 0xff,
482 0xe1, 0x06, 0x06, 0x01, 0xff, 0x00, 0x01, 0x00,
483 0x08, 0x00, 0xfa, 0x00, 0xff, 0xff, 0xff, 0xff,
484 0x08, 0x01, 0x00, 0xff, 0x01, 0xff, 0x00, 0x00,
485 0xf5, 0xff, 0x00, 0x01, 0xff, 0x01, 0x01, 0x00,
486 0xff, 0xff, 0x01, 0xff, 0x01, 0x00, 0x01, 0x00,
487 0x00, 0x01, 0x01, 0xff, 0x00, 0xff, 0x00, 0x01,
488 0x02, 0x00, 0x00, 0xff, 0xff, 0x00, 0xff, 0x00,
489 },
490 }
491
View as plain text