| 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
Condition100%9/9
$vector and ref $vector eq "ARRAY" and $vector->[0] and ref $vector->[0] eq "ARRAY"
$vector and ref $vector eq "ARRAY" and $vector->[0]
$vector and ref $vector eq "ARRAY"
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"
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
$dim == 1 or $dim == $sz
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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 102 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 103 | 14 | my $pack; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 104 | 14 | ▶ | for (my $x = 0; $x < $dim; $x++) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 105 | 131 | $pack .= pack "d$sz", @{$vector->[$x]} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 106 | } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 107 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 108 | 14 | ▶ | if ($dim > 1) { | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 109 | 7 | ▶ | $sz == 8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
MC/DC100%2/2
shift() || sqrt scalar @$input
shift()
sqrt scalar @$input
Truth table100%3/3
A || B
A= shift()B= sqrt scalar @$input
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 185 | 9 | my $pack = pack "d".($sz*$sz), @$input; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 186 | 9 | ▶ | $sz == 8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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
MC/DC0%0/2
shift() || sqrt scalar @$input
shift()
sqrt scalar @$input
Truth table66%2/3
A || B
A= shift()B= sqrt scalar @$input
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||