blib/lib/Math/DCT.pm

filter: Statementstmt 100% 59 / 59 Branchbran 100% 24 / 24 Conditioncond 94.4% 17 / 18 MC/DCmcdc 80.0% 8 / 10 Subroutinesub 100% 9 / 9 Podpod 100% 5 / 5 totaltotal 97.6% 122 / 125 CC 20 SCAR 21.1
CC
20
Cov
99%
dct
14.0
dct2d
4.0
dct1d
3.0
CRAP 8.2
↑ Summary DCT.xs »
1 package Math::DCT;
2  
3 4 ▶use 5.008;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 4 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 4 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 =encoding UTF-8
8  
9 =head1 NAME
10  
11 Math::DCT - 1D and NxN 2D Fast Discreet Cosine Transforms (DCT-II)
12  
13 =head1 SYNOPSIS
14  
15 use Math::DCT qw/dct dct1d dct2d idct1d idct2d/;
16  
17 # DCT of 1D array
18 my $dct1d = dct([[1,2,3,4]]);
19 $dct1d = dct1d([1,2,3,4]);
20  
21 # DCT of 2D array
22 my $dct2d = dct([[1,2],[3,4]]);
23 $dct2d = dct2d([1,2,3,4]);
24  
25 # iDCT of 1D and 2D array
26 my $idct1d = idct1d([1,2,3,4]);
27 my $idct2d = idct2d([1,2,3,4]);
28  
29 =head1 VERSION
30  
31 Version 0.04
32  
33 =cut
34  
35 4 our $VERSION = '0.04';
36  
37 4 require XSLoader;
38 4 XSLoader::load('Math::DCT', $VERSION);
39  
40 4 ▶use Exporter qw(import);
Subroutine BEGIN: called CC=1 SCAR=0.0
41  
42 4 our @EXPORT_OK = qw(
43 dct
44 dct1d
45 dct2d
46 idct1d
47 idct2d
48 );
49  
50 4 our %EXPORT_TAGS;
51 4 $EXPORT_TAGS{all} = [@EXPORT_OK];
52  
53 =head1 DESCRIPTION
54  
55 An unscaled DCT-II implementation for 1D and NxN 2D matrices implemented in XS.
56 For array sizes which are a power of 2 a fast - I<O(n logn)> for 1D, I<O(n² logn)>
57 for 2D - algorithm (FCT) described by Lee is used with some tweaks.
58 In addition, an unscaled version of the specially optimized Arai, Agui, Nakajima
59 FCT is used for 1x8, 8x8 matrices. A less optimized algorithm is used for
60 the generic case, so any 1D or square 2D matrix can be processed (I<O(n²)>,
61 I<O(n³)> respectivelly).
62  
63 For convenience the inverse functions are provided (inverse DCT-II, usually called
64 iDCT, is essentially a scaled DCT-III), with an implementation equivalent to the
65 generic DCT-II case.
66  
67 The module was written for a perceptual hash project that needed 32x32 DCT-II, and
68 on a 2.5GHz i7 2015 Macbook Pro about 18000/s per thread are processed.
69 The common 8x8 DCT-II uses a special path, (about 380000/s on that same CPU),
70 although for most image/video applications that require 8x8 DCT there are much faster
71 implementations (SIMD, approximations etc) that usually produce an already scaled result
72 for the specific application.
73  
74 None of the algorithms used on this module are approximate, the test suite verifies
75 against a naive DCT-II implementation with a tolerance of 1e-08.
76  
77 =head1 METHODS
78
79 =head2 C<dct>
80  
81 my $dct = dct([[1,2],[3,4]]); # Example for 2x2 2D matrix
82  
83 Pass an array (ref) of either a single array, or N x length-N arrays for 1D and NxN
84 2D DCT-II calculation respectivelly. The output will be an arrayref of array(s)
85 with the result of the transform.
86  
87 It is a convenience function with some overhead, mainly in the case of NxN arrays
88 which have to be flattened before processing - for already flat 2D data see L<dct2d>
89 below.
90  
91 =cut
92  
93 19 ▶sub dct {
Subroutine dct: called CC=14 SCAR=26.4
Pod documented
94 19 my $vector = shift;
95 19 ▶ die "Expect array of array(s)"
Branch: 1 branch
BranchTrueFalseTotal
unless $vector and ref $vector eq "ARRAY" and $vector->[0] and ref $vector->[0] eq "ARRAY" 4 15 19
Condition100%9/9
$vector and ref $vector eq "ARRAY" and $vector->[0] and ref $vector->[0] eq "ARRAY"
!ll&&!rl&&r
3115
$vector and ref $vector eq "ARRAY" and $vector->[0]
!ll&&!rl&&r
2116
$vector and ref $vector eq "ARRAY"
!ll&&!rl&&r
1117
MC/DC100%4/4
$vector and ref $vector eq "ARRAY" and $vector->[0] and ref $vector->[0] eq "ARRAY"
$vector ref $vector eq "ARRAY" $vector->[0] ref $vector->[0] eq "ARRAY"
Truth table100%5/5
A and B and C and D
A= $vectorB= ref $vector eq "ARRAY"C= $vector->[0]D= ref $vector->[0] eq "ARRAY"
ABCDresult
0XXX0
10XX0
110X0
11100
11111
96 unless $vector && ref $vector eq 'ARRAY'
97 && $vector->[0] && ref $vector->[0] eq 'ARRAY';
98  
99 15 my $dim = scalar(@$vector);
100 15 my $sz = scalar(@{$vector->[0]});
101 15 ▶ die "Expect 1d or NxN 2d arrays" unless $dim == 1 || $dim == $sz;
Branch: 1 branch
BranchTrueFalseTotal
unless $dim == 1 or $dim == $sz 1 14 15
Condition100%3/3
$dim == 1 or $dim == $sz
l!l&&r!l&&!r
771
MC/DC100%2/2
$dim == 1 or $dim == $sz
$dim == 1 $dim == $sz
Truth table100%3/3
A or B
A= $dim == 1B= $dim == $sz
ABresult
1X1
011
000
102  
103 14 my $pack;
104 14 ▶ for (my $x = 0; $x < $dim; $x++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($x < $dim) 131 14 145
105 131 $pack .= pack "d$sz", @{$vector->[$x]}
106 }
107  
108 14 ▶ if ($dim > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($dim > 1) { } 7 7 14
109 7 ▶ $sz == 8
Branch: 2 branches
BranchTrueFalseTotal
$sz == 8 ? : 1 6 7
0 == ($sz & $sz - 1) ? : 4 2 6
110 ? fct8_2d($pack)
111 : 0 == ($sz & ($sz - 1)) ? fast_dct_2d($pack, $sz) : dct_2d($pack, $sz);
112 } else {
113 7 ▶ $sz == 8
Branch: 2 branches
BranchTrueFalseTotal
$sz == 8 ? : 1 6 7
0 == ($sz & $sz - 1) ? : 4 2 6
114 ? fct8_1d($pack)
115 : 0 == ($sz & ($sz - 1)) ? fast_dct_1d($pack, $sz) : dct_1d($pack, $sz);
116 }
117  
118 14 my $result;
119 14 foreach (0..$dim-1) {
120 131 $result->[$_] = [unpack "d".($sz), substr $pack, $_ * $sz*8, $sz*8];
121 }
122 14 return $result;
123 }
124  
125 =head2 C<dct1d>
126  
127 my $dct = dct1d([1,2,3]);
128  
129 Pass an array (ref) for a 1D DCT-II calculation. The output will be an arrayref
130 with the result of the transform.
131  
132 =cut
133  
134 7 ▶sub dct1d {
Subroutine dct1d: called CC=3 SCAR=11.0
Pod documented
135 7 my $input = shift;
136 7 my $sz = scalar @$input;
137 7 my $pack = pack "d$sz", @$input;
138 7 ▶ $sz == 8
Branch: 2 branches
BranchTrueFalseTotal
$sz == 8 ? : 1 6 7
0 == ($sz & $sz - 1) ? : 4 2 6
139 ? fct8_1d($pack)
140 : 0 == ($sz & ($sz - 1)) ? fast_dct_1d($pack, $sz) : dct_1d($pack, $sz);
141 7 my @result = unpack "d$sz", $pack;
142 7 return \@result;
143 }
144  
145 =head2 C<idct1d>
146  
147 my $idct = idct1d([1,2,3]);
148  
149 Pass an array (ref) for a 1D iDCT calculation. The output will be an arrayref
150 with the result of the transform. This is essentially a DCT-III transform scaled
151 by 2/N.
152  
153 =cut
154  
155 6 ▶sub idct1d {
Subroutine idct1d: called CC=1 SCAR=0.0
Pod documented
156 6 my $input = shift;
157 6 my $sz = scalar @$input;
158 6 my $pack = pack "d$sz", @$input;
159 6 idct_1d($pack, $sz);
160 6 my @result = unpack "d$sz", $pack;
161 6 return \@result;
162 }
163  
164 =head2 C<dct2d>
165  
166 my $dct = dct2d(
167 [1,2,3,4], # Arrayref containing your NxN matrix
168 2 # Optionally, the size N of your array (sqrt of its length)
169 );
170  
171 Pass an array (ref) for a 2D DCT-II calculation. The length of the array is expected
172 to be a square (as only NxN arrays are supported) - you can optionally pass N as
173 the second argument to avoid a C<sqrt> calculation.
174 The output will be an arrayref with the result of the transform.
175  
176 If your 2D data is available in a 1D array as is usual with most image manipulation
177 etc cases, this function will be faster than C<dct>, as the DCT calculation is
178 anyway done on a flattened (1D) array, hence you skip the conversion.
179  
180 =cut
181  
182 10 ▶sub dct2d {
Subroutine dct2d: called CC=4 SCAR=13.9
Pod documented
183 10 my $input = shift;
184 10 ▶ my $sz = shift || sqrt(scalar @$input);
Condition100%3/3
shift() || sqrt scalar @$input
l!l&&r!l&&!r
172
MC/DC100%2/2
shift() || sqrt scalar @$input
shift() sqrt scalar @$input
Truth table100%3/3
A || B
A= shift()B= sqrt scalar @$input
ABresult
1X1
011
000
185 9 my $pack = pack "d".($sz*$sz), @$input;
186 9 ▶ $sz == 8
Branch: 2 branches
BranchTrueFalseTotal
$sz == 8 ? : 1 8 9
0 == ($sz & $sz - 1) ? : 6 2 8
187 ? fct8_2d($pack)
188 : 0 == ($sz & ($sz - 1)) ? fast_dct_2d($pack, $sz) : dct_2d($pack, $sz);
189 9 my @result = unpack "d".($sz*$sz), $pack;
190 9 return \@result;
191 }
192  
193 =head2 C<idct2d>
194  
195 my $idct = idct2d(
196 [1,2,3,4], # Arrayref containing your NxN matrix
197 2 # Optionally, the size N of your array (sqrt of its length)
198 );
199  
200 Pass an array (ref) for a 2D iDCT calculation. The length of the array is expected
201 to be a square (as only NxN arrays are supported) - you can optionally pass N as
202 the second argument to avoid a C<sqrt> calculation.
203 This is essentially a DCT-III transform scaled by 2/N.
204 The output will be an arrayref with the result of the transform.
205  
206 =cut
207  
208 7 ▶sub idct2d {
Subroutine idct2d: called CC=2 SCAR=7.0
Pod documented
209 7 my $input = shift;
210 7 ▶ my $sz = shift || sqrt(scalar @$input);
Condition66%2/3
shift() || sqrt scalar @$input
l!l&&r!l&&!r
160
MC/DC0%0/2
shift() || sqrt scalar @$input
shift() sqrt scalar @$input
Truth table66%2/3
A || B
A= shift()B= sqrt scalar @$input
ABresult
1X1
011
000
211 7 my $pack = pack "d".($sz*$sz), @$input;
212 7 idct_2d($pack, $sz);
213 7 my @result = unpack "d".($sz*$sz), $pack;
214 7 return \@result;
215 }
216  
217 =head1 USAGE NOTES
218  
219 The C functions are not exported, but theoretically you could use them directly
220 if you do your own C<pack/unpack>. The fast versions for power-of-2 size arrays
221 are C<fast_dct_1d> and C<fast_dct_2d>, while the generic versions are C<dct_1d>
222 and C<dct_2d> (with their inverse functions being C<idct_1d> and C<idct_2d>).
223 The specialized size-8 versions are C<fct8_1d> and C<fct8_2d>.
224 First argument is a C<char *> (use C<pack "dN">), second is the size N (except
225 for the fct8* functions which don't need a second argument).
226  
227 There is a simple benchmarking script available (C<bench/benchmarking.pl>).
228 Sample output (on an Apple M1 CPU):
229  
230 ** Fast 2D DCT-II (Arai et al.) **
231 8x8: 688910/s
232 ** Fast 2D DCT-II (Lee) **
233 32x32: 34501/s
234 64x64: 8471/s
235 256x256: 438/s
236 ** Generic 2D DCT-II **
237 24x24: 49898/s
238 48x48: 7616/s
239 ** Generic 2D iDCT **
240 8x8: 516756/s
241 32x32: 24187/s
242  
243 =head1 ACKNOWLEDGEMENTS
244  
245 C-code for 1D DCT was adapted from Project Nayuki and improved where possible.
246  
247 (L<https://www.nayuki.io/page/fast-discrete-cosine-transform-algorithms>)
248  
249 =head1 AUTHOR
250  
251 Dimitrios Kechagias, C<< <dkechag at cpan.org> >>
252
253 =head1 BUGS
254  
255 Please report any bugs or feature requests either on GitHub, or on RT (via the email
256 C<bug-math-dct at rt.cpan.org> or web interface at L<https://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-DCT>).
257  
258 I will be notified, and then you'll be notified of progress on your bug as I make changes.
259  
260 =head1 GIT
261  
262 L<https://github.com/SpareRoom/Math-DCT>
263
264 =head1 COPYRIGHT & LICENSE
265  
266 Copyright (C) 2019, SpareRoom.com
267  
268 This program is free software; you can redistribute
269 it and/or modify it under the same terms as Perl itself.
270  
271 =cut
272  
273 4 1;
↑ Summary DCT.xs »