DCT.xs

filter: Statementstmt 96.6% 231 / 239 Branchbran 91.4% 86 / 94 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 95.2% 317 / 333 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Math/DCT.pm ↑ Summary
1 // Author: Dimitrios Kechagias, dkechag at cpan.org
2 // Copyright (C) 2019, SpareRoom.com
3 // This program is free software; you can redistribute
4 // it and/or modify it under the same terms as Perl itself.
5 // Significant code adapted from:
6  
7 /*
8 * Fast discrete cosine transform algorithms (C)
9 *
10 * Copyright (c) 2017 Project Nayuki. (MIT License)
11 * https://www.nayuki.io/page/fast-discrete-cosine-transform-algorithms
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining a copy of
14 * this software and associated documentation files (the "Software"), to deal in
15 * the Software without restriction, including without limitation the rights to
16 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
17 * the Software, and to permit persons to whom the Software is furnished to do so,
18 * subject to the following conditions:
19 * - The above copyright notice and this permission notice shall be included in
20 * all copies or substantial portions of the Software.
21 * - The Software is provided "as is", without warranty of any kind, express or
22 * implied, including but not limited to the warranties of merchantability,
23 * fitness for a particular purpose and noninfringement. In no event shall the
24 * authors or copyright holders be liable for any claim, damages or other
25 * liability, whether in an action of contract, tort or otherwise, arising from,
26 * out of or in connection with the Software or the use or other dealings in the
27 * Software.
28 */
29  
30 #include "EXTERN.h"
31 #include "perl.h"
32 #include "XSUB.h"
33  
34 #ifndef M_PI
35 #define M_PI 3.14159265358979323846
36 #endif
37  
38 void transform_recursive(double input[], double temp[], int size, double coef[]);
39  
40 34 void fct8_1d(char *inbuf) {
41 34 double *vector = (double *) inbuf;
42  
43 34 const double v0 = vector[0] + vector[7];
44 34 const double v1 = vector[1] + vector[6];
45 34 const double v2 = vector[2] + vector[5];
46 34 const double v3 = vector[3] + vector[4];
47 34 const double v4 = vector[3] - vector[4];
48 34 const double v5 = vector[2] - vector[5];
49 34 const double v6 = vector[1] - vector[6];
50 34 const double v7 = vector[0] - vector[7];
51  
52 34 const double v8 = v0 + v3;
53 34 const double v9 = v1 + v2;
54 34 const double v10 = v1 - v2;
55 34 const double v11 = v0 - v3;
56 34 const double v12 = -v4 - v5;
57 34 const double v13 = (v5 + v6) * 0.707106781186547524400844;
58 34 const double v14 = v6 + v7;
59  
60 34 const double v15 = v8 + v9;
61 34 const double v16 = v8 - v9;
62 34 const double v17 = (v10 + v11) * 0.707106781186547524400844;
63 34 const double v18 = (v12 + v14) * 0.382683432365089771728460;
64  
65 34 const double v19 = -v12 * 0.541196100146196984399723 - v18;
66 34 const double v20 = v14 * 1.306562964876376527856643 - v18;
67  
68 34 const double v21 = v17 + v11;
69 34 const double v22 = v11 - v17;
70 34 const double v23 = v13 + v7;
71 34 const double v24 = v7 - v13;
72  
73 34 const double v25 = v19 + v24;
74 34 const double v26 = v23 + v20;
75 34 const double v27 = v23 - v20;
76 34 const double v28 = v24 - v19;
77  
78 34 vector[0] = v15;
79 34 vector[1] = 0.509795579104157595 * v26;
80 34 vector[2] = 0.54119610014619577 * v21;
81 34 vector[3] = 0.60134488693504412 * v28;
82 34 vector[4] = 0.707106781186547 * v16;
83 34 vector[5] = 0.8999762231364133 * v25;
84 34 vector[6] = 1.30656296487637502 * v22;
85 34 vector[7] = 2.5629154477415022505 * v27;
86 34 }
87  
88 2 void fct8_2d(
89 char *inbuf)
90 {
91 2 double *input = (double *) inbuf;
92 double temp[64];
93 int x,y;
94  
95 18 ▶ for (x = 0; x < 64; x+=8) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < 64; x+=8) { 16 2 18
96 16 fct8_1d((char *)&input[x]);
97 }
98  
99 18 ▶ for (x = 0; x < 8; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < 8; x++) { 16 2 18
100 144 ▶ for (y = 0; y < 8; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < 8; y++) { 128 16 144
101 128 temp[y*8+x]=input[x*8+y];
102 }
103 }
104  
105 18 ▶ for (y = 0; y < 64; y+=8) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < 64; y+=8) { 16 2 18
106 16 fct8_1d((char *)&temp[y]);
107 }
108  
109 18 ▶ for (x = 0; x < 8; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < 8; x++) { 16 2 18
110 144 ▶ for (y = 0; y < 8; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < 8; y++) { 128 16 144
111 128 input[y*8+x]=temp[x*8+y];
112 }
113 }
114 2 }
115  
116 4 void dct_1d(
117 char *inbuf,
118 int size)
119 4 {
120 4 double *input = (double *) inbuf;
121 4 double temp[size];
122 4 double factor = M_PI/size;
123  
124 int i,j;
125 32 ▶ for(i = 0; i < size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < size; ++i) { 28 4 32
126 28 double sum = 0;
127 28 double mult = i*factor;
128 288 ▶ for(j = 0; j < size; ++j) {
Branch: 1 branch
BranchTrueFalseTotal
for(j = 0; j < size; ++j) { 260 28 288
129 260 sum += input[j] * cos((j+0.5)*mult);
130 }
131 28 temp[i]=sum;
132 }
133  
134 32 ▶ for(i = 0; i < size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < size; ++i) { 28 4 32
135 28 input[i]=temp[i];
136 }
137 4 }
138  
139 6 void idct_1d(
140 char *inbuf,
141 int size)
142 6 {
143 6 double *input = (double *) inbuf;
144 6 double temp[size];
145 6 double factor = M_PI/size;
146 6 float scale = 2.0 / size;
147  
148 int i,j;
149 128 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 122 6 128
150 122 double sum = input[0] / 2.0;
151 122 double mult = (i+0.5)*factor;
152 5330 ▶ for (j = 1; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 1; j < size; j++) { 5208 122 5330
153 5208 sum += input[j] * cos(j*mult);
154 }
155 122 temp[i] = sum;
156 }
157  
158 128 ▶ for(i = 0; i < size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for(i = 0; i < size; ++i) { 122 6 128
159 122 input[i]=temp[i] * scale;
160 }
161 6 }
162  
163 4 void dct_coef(int size, double coef[size][size]) {
164 4 double factor = M_PI/size;
165  
166 int i, j;
167 32 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 28 4 32
168 28 double mult = i*factor;
169 288 ▶ for (j = 0; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < size; j++) { 260 28 288
170 260 coef[j][i] = cos((j+0.5)*mult);
171 }
172 }
173 4 }
174  
175 7 void idct_coef(int size, double coef[size][size]) {
176 7 double factor = M_PI/size;
177  
178 int i, j;
179 131 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 124 7 131
180 124 double mult = (i+0.5)*factor;
181 5458 ▶ for (j = 0; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < size; j++) { 5334 124 5458
182 5334 coef[j][i] = cos(j*mult);
183 }
184 }
185 7 }
186  
187 4 void dct_2d(
188 char *inbuf,
189 int size)
190 4 {
191 4 double *input = (double *) inbuf;
192 4 double coef[size][size];
193 4 double temp[size*size];
194 int x, y, i, j;
195  
196 4 dct_coef(size, coef);
197  
198 32 ▶ for (x = 0; x < size; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < size; x++) { 28 4 32
199 288 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 260 28 288
200 260 double sum = 0;
201 260 y = x * size;
202 2976 ▶ for (j = 0; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < size; j++) { 2716 260 2976
203 2716 sum += input[y+j] * coef[j][i];
204 }
205 260 temp[y+i] = sum;
206 }
207 }
208  
209 32 ▶ for (y = 0; y < size; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < size; y++) { 28 4 32
210 288 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 260 28 288
211 260 double sum = 0;
212 2976 ▶ for (j = 0; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < size; j++) { 2716 260 2976
213 2716 sum += temp[j*size+y] * coef[j][i];
214 }
215 260 input[i*size+y] = sum;
216 }
217 }
218 4 }
219  
220 7 void idct_2d(
221 char *inbuf,
222 int size)
223 7 {
224 7 double *input = (double *) inbuf;
225 7 double coef[size][size];
226 7 double temp[size*size];
227 7 float scale = 2.0 / size;
228 int x, y, i, j;
229  
230 7 idct_coef(size, coef);
231  
232 131 ▶ for (x = 0; x < size; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < size; x++) { 124 7 131
233 5458 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 5334 124 5458
234 5334 double sum = input[x*size] / 2.0;
235 5334 y = x * size;
236 296854 ▶ for (j = 1; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 1; j < size; j++) { 291520 5334 296854
237 291520 sum += input[y+j] * coef[j][i];
238 }
239 5334 temp[y+i] = sum * scale;
240 }
241 }
242  
243 131 ▶ for (y = 0; y < size; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < size; y++) { 124 7 131
244 5458 ▶ for (i = 0; i < size; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; i++) { 5334 124 5458
245 5334 double sum = temp[y] / 2.0;
246 296854 ▶ for (j = 1; j < size; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 1; j < size; j++) { 291520 5334 296854
247 291520 sum += temp[j*size+y] * coef[j][i];
248 }
249 5334 input[i*size+y] = sum * scale;
250 }
251 }
252 7 }
253  
254 420 void fast_dct_1d_precalc(
255 char *inbuf,
256 int size,
257 double coef[])
258 420 {
259 420 double *input = (double *) inbuf;
260 420 double temp[size];
261  
262 420 transform_recursive(input, temp, size, coef);
263 420 }
264  
265 18 void fast_dct_coef(int size, double coef[size]) {
266  
267 int i, j;
268 77 ▶ for (i = 1; i <= size/2; i*=2) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i <= size/2; i*=2) { 59 18 77
269 59 double factor = M_PI/(i*2);
270 456 ▶ for (j = 0; j < i; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < i; j++) { 397 59 456
271 397 coef[i+j] = cos((j+0.5)*factor)*2;
272 }
273 }
274 18 }
275  
276 8 void fast_dct_1d(
277 char *inbuf,
278 int size)
279 8 {
280 8 double coef[size];
281  
282 8 fast_dct_coef(size, coef);
283  
284 8 fast_dct_1d_precalc(inbuf, size, coef);
285 8 }
286  
287 10 void fast_dct_2d(
288 char *inbuf,
289 int size)
290 10 {
291 10 double *input = (double *) inbuf;
292 10 double coef[size];
293 10 double temp[size*size];
294 int x,y,k;
295  
296 10 fast_dct_coef(size, coef);
297  
298 216 ▶ for (x = 0; x < size*size; x+=size) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < size*size; x+=size) { 206 10 216
299 206 fast_dct_1d_precalc((char *)&input[x], size, coef);
300 }
301  
302 216 ▶ for (x = 0; x < size; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < size; x++) { 206 10 216
303 206 k = x * size;
304 10490 ▶ for (y = 0; y < size; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < size; y++) { 10284 206 10490
305 10284 temp[y*size+x]=input[k++];
306 }
307 }
308  
309 216 ▶ for (y = 0; y < size*size; y+=size) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < size*size; y+=size) { 206 10 216
310 206 fast_dct_1d_precalc((char *)&temp[y], size, coef);
311 }
312  
313 216 ▶ for (x = 0; x < size; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < size; x++) { 206 10 216
314 206 k = x * size;
315 10490 ▶ for (y = 0; y < size; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < size; y++) { 10284 206 10490
316 10284 input[y*size+x]=temp[k++];
317 }
318 }
319 10 }
320  
321 41132 void transform_recursive(double input[], double temp[], int size, double coef[]) {
322 41132 ▶ if (size == 1)
Branch: 1 branch
BranchTrueFalseTotal
if (size == 1) 20776 20356 41132
323 20776 return;
324  
325 int i,j;
326 20356 int half = size / 2;
327  
328 80384 ▶ for (i = 0; i < half; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < half; i++) { 60028 20356 80384
329 60028 double x = input[i];
330 60028 double y = input[size-1-i];
331 60028 temp[i] = x+y;
332 60028 temp[i+half] = (x-y)/coef[half+i];
333 }
334  
335 20356 transform_recursive(temp, input, half, coef);
336 20356 transform_recursive(&temp[half], input, half, coef);
337  
338 20356 j = 0;
339 60028 ▶ for (i = 0; i < half-1; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < half-1; i++) { 39672 20356 60028
340 39672 input[j++] = temp[i];
341 39672 input[j++] = temp[i+half] + temp[i+half+1];
342 }
343 20356 input[size-2] = temp[half-1];
344 20356 input[size-1] = temp[size-1];
345 }
346  
347  
348 MODULE = Math::DCT PACKAGE = Math::DCT
349  
350 PROTOTYPES: DISABLE
351  
352  
353 void
354 fct8_1d (inbuf)
355 char * inbuf
356 PREINIT:
357 I32* temp;
358 PPCODE:
359 2 temp = PL_markstack_ptr++;
360 2 fct8_1d(inbuf);
361 2 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 2 0 2
362 /* truly void, because dXSARGS not invoked */
363 2 PL_markstack_ptr = temp;
364 2 XSRETURN_EMPTY; /* return empty stack */
365 }
366 /* must have used dXSARGS; list context implied */
367 0 return; /* assume stack size is correct */
368  
369 void
370 fct8_2d (inbuf)
371 char * inbuf
372 PREINIT:
373 I32* temp;
374 PPCODE:
375 2 temp = PL_markstack_ptr++;
376 2 fct8_2d(inbuf);
377 2 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 2 0 2
378 /* truly void, because dXSARGS not invoked */
379 2 PL_markstack_ptr = temp;
380 2 XSRETURN_EMPTY; /* return empty stack */
381 }
382 /* must have used dXSARGS; list context implied */
383 0 return; /* assume stack size is correct */
384  
385 void
386 dct_1d (inbuf, size)
387 char * inbuf
388 int size
389 PREINIT:
390 I32* temp;
391 PPCODE:
392 4 temp = PL_markstack_ptr++;
393 4 dct_1d(inbuf, size);
394 4 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 4 0 4
395 /* truly void, because dXSARGS not invoked */
396 4 PL_markstack_ptr = temp;
397 4 XSRETURN_EMPTY; /* return empty stack */
398 }
399 /* must have used dXSARGS; list context implied */
400 0 return; /* assume stack size is correct */
401  
402 void
403 idct_1d (inbuf, size)
404 char * inbuf
405 int size
406 PREINIT:
407 I32* temp;
408 PPCODE:
409 6 temp = PL_markstack_ptr++;
410 6 idct_1d(inbuf, size);
411 6 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 6 0 6
412 /* truly void, because dXSARGS not invoked */
413 6 PL_markstack_ptr = temp;
414 6 XSRETURN_EMPTY; /* return empty stack */
415 }
416 /* must have used dXSARGS; list context implied */
417 0 return; /* assume stack size is correct */
418  
419 void
420 dct_2d (inbuf, size)
421 char * inbuf
422 int size
423 PREINIT:
424 I32* temp;
425 PPCODE:
426 4 temp = PL_markstack_ptr++;
427 4 dct_2d(inbuf, size);
428 4 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 4 0 4
429 /* truly void, because dXSARGS not invoked */
430 4 PL_markstack_ptr = temp;
431 4 XSRETURN_EMPTY; /* return empty stack */
432 }
433 /* must have used dXSARGS; list context implied */
434 0 return; /* assume stack size is correct */
435  
436 void
437 idct_2d (inbuf, size)
438 char * inbuf
439 int size
440 PREINIT:
441 I32* temp;
442 PPCODE:
443 7 temp = PL_markstack_ptr++;
444 7 idct_2d(inbuf, size);
445 7 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 7 0 7
446 /* truly void, because dXSARGS not invoked */
447 7 PL_markstack_ptr = temp;
448 7 XSRETURN_EMPTY; /* return empty stack */
449 }
450 /* must have used dXSARGS; list context implied */
451 0 return; /* assume stack size is correct */
452  
453 void
454 fast_dct_1d (inbuf, size)
455 char * inbuf
456 int size
457 PREINIT:
458 I32* temp;
459 PPCODE:
460 8 temp = PL_markstack_ptr++;
461 8 fast_dct_1d(inbuf, size);
462 8 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 8 0 8
463 /* truly void, because dXSARGS not invoked */
464 8 PL_markstack_ptr = temp;
465 8 XSRETURN_EMPTY; /* return empty stack */
466 }
467 /* must have used dXSARGS; list context implied */
468 0 return; /* assume stack size is correct */
469  
470 void
471 fast_dct_2d (inbuf, size)
472 char * inbuf
473 int size
474 PREINIT:
475 I32* temp;
476 PPCODE:
477 10 temp = PL_markstack_ptr++;
478 10 fast_dct_2d(inbuf, size);
479 10 ▶ if (PL_markstack_ptr != temp) {
Branch: 1 branch
BranchTrueFalseTotal
if (PL_markstack_ptr != temp) { 10 0 10
480 /* truly void, because dXSARGS not invoked */
481 10 PL_markstack_ptr = temp;
482 10 XSRETURN_EMPTY; /* return empty stack */
483 }
484 /* must have used dXSARGS; list context implied */
485 0 return; /* assume stack size is correct */
486  
« blib/lib/Math/DCT.pm ↑ Summary