lib/Peta/Vorbis/Encode/Book.pm

filter: Statementstmt 94.8% 110 / 116 Branchbran 73.8% 31 / 42 Conditioncond 72.4% 21 / 29 MC/DCmcdc 50.0% 8 / 16 Subroutinesub 82.3% 14 / 17 Podpod 100% 11 / 11 totaltotal 84.4% 195 / 231 CC 43 SCAR 19.4
CC
43
Cov
87%
_take
13.1
_lengths
9.3
float32
6.8
CRAP 6.9
« lib/Peta/MIDI/Encoder.pm ↑ Summary lib/Peta/MIDI/Event.pm »
1 package Peta::Vorbis::Encode::Book;
2 # ABSTRACT: a Vorbis codebook
3  
4 # A Vorbis codebook: entries, each with a codeword, and for the residue's
5 # books a vector of values per entry (a lattice: lookup type 1).
6 #
7 # The codeword lengths come from weights (how often an entry is expected)
8 # by Huffman's construction; the codewords themselves are assigned as the
9 # Vorbis I specification defines them: entry after entry, each the lowest
10 # valued codeword of its length that is still free (the leftmost free
11 # place of that depth in the code tree). A complete tree is checked: the
12 # lengths must fill it exactly.
13 #
14 # A lattice book of dimension d over m values (value j being minimum + j *
15 # delta) has m^d entries; entry e's value i is value number (e / m^i) % m.
16  
17 1 ▶use v5.36;
Subroutine BEGIN: called CC=1 SCAR=0.0
18 1 ▶use List::Util qw(max);
Subroutine BEGIN: called CC=1 SCAR=0.0
19  
20 1 our $VERSION = '0.2610180';
21  
22 1 ▶use constant SYNC => 0x564342;
Subroutine BEGIN: called CC=1 SCAR=0.0
23  
24 # new(dimensions => d, values => m, delta => ..., minimum => ..., weights => \@w)
25 # for a lattice book; new(entries => n, weights => \@w) for a scalar book
26 # (no values: floors and classifications).
27 19 ▶sub new ($class, %arg) {
Subroutine new: called CC=5 SCAR=16.1
Pod documented
28 19 ▶ my $dim = $arg{dimensions} // 1;
Condition100%2/2
$arg{"dimensions"} // 1
l!l
172
MC/DC100%1/1
$arg{"dimensions"} // 1
$arg{"dimensions"}
Truth table100%2/2
A
A= $arg{"dimensions"}
Aresult
11
00
29 19 my $m = $arg{values};
30 19 ▶ my $entries = $m ? $m**$dim : $arg{entries};
Branch: 1 branch
BranchTrueFalseTotal
$m ? : 15 4 19
31 19 ▶ my $w = $arg{weights} // [ (1) x $entries ];
Condition100%2/2
$arg{"weights"} // [(1) x $entries]
l!l
181
MC/DC100%1/1
$arg{"weights"} // [(1) x $entries]
$arg{"weights"}
Truth table100%2/2
A
A= $arg{"weights"}
Aresult
11
00
32 19 ▶ die "weights for $entries entries, not " . @$w . "\n" if @$w != $entries;
Branch: 1 branch
BranchTrueFalseTotal
if @$w != $entries 0 19 19
33  
34 19 my $lengths = _lengths($w);
35 return bless {
36 dim => $dim,
37 m => $m,
38 entries => $entries,
39 delta => $arg{delta},
40 minimum => $arg{minimum},
41 19 lengths => $lengths,
42 codes => _codes($lengths),
43 }, $class;
44 }
45  
46 0 ▶sub entries ($self) { return $self->{entries} }
Subroutine entries: not called CC=1 SCAR=6.9
Pod documented
47 1212 ▶sub dimensions ($self) { return $self->{dim} }
Subroutine dimensions: called CC=1 SCAR=0.0
Pod documented
48 1 ▶sub lengths ($self) { return $self->{lengths} }
Subroutine lengths: called CC=1 SCAR=0.0
Pod documented
49  
50 # The codeword lengths of a Huffman code for the weights, none longer than
51 # 32 bits (Vorbis' limit): weights too small to matter are raised.
52 19 ▶sub _lengths ($w) {
Subroutine _lengths: called CC=9 SCAR=22.3
53 19 my $n = @$w;
54 19 ▶ return [1] if $n == 1; # a single entry: one bit (Vorbis I errata)
Branch: 1 branch
BranchTrueFalseTotal
if $n == 1 0 19 19
55  
56 19 my $total = 0;
57 19 $total += $_ for @$w;
58  
59 19 for my $floor (1e-9, 1e-7, 1e-5, 1e-3) {
60 19 my $least = $floor * $total;
61  
62 # Merge the two lightest trees, until one is left; each entry's
63 # depth is how often its tree was merged.
64 19 my @depth = (0) x $n;
65 19 my @members = map { [$_] } 0 .. $n - 1;
66 19 ▶ my @heap = map { [ ($w->[$_] > $least ? $w->[$_] : $least), $_ ] } 0 .. $n - 1;
Branch: 1 branch
BranchTrueFalseTotal
$w->[$_] > $least ? : 1111 0 1111
67 19 ▶ while (@heap > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@heap > 1) 1092 19 1111
68 1092 ▶ @heap = sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @heap;
Condition66%2/3
$Peta::Vorbis::Encode::Book::a->[0] <=> $Peta::Vorbis::Encode::Book::b->[0] || $Peta::Vorbis::Encode::Book::a->[1] <=> $Peta::Vorbis::Encode::Book::b->[1]
l!l&&r!l&&!r
5743256430
MC/DC0%0/2
$Peta::Vorbis::Encode::Book::a->[0] <=> $Peta::Vorbis::Encode::Book::b->[0] || $Peta::Vorbis::Encode::Book::a->[1] <=> $Peta::Vorbis::Encode::Book::b->[1]
$Peta::Vorbis::Encode::Book::a->[0] <=> $Peta::Vorbis::Encode::Book::b->[0] $Peta::Vorbis::Encode::Book::a->[1] <=> $Peta::Vorbis::Encode::Book::b->[1]
Truth table66%2/3
A || B
A= $Peta::Vorbis::Encode::Book::a->[0] <=> $Peta::Vorbis::Encode::Book::b->[0]B= $Peta::Vorbis::Encode::Book::a->[1] <=> $Peta::Vorbis::Encode::Book::b->[1]
ABresult
1X1
011
000
69 1092 my ($x, $y) = splice @heap, 0, 2;
70 1092 my @both = (@{ $members[ $x->[1] ] }, @{ $members[ $y->[1] ] });
71 1092 $depth[$_]++ for @both;
72 1092 $members[ $x->[1] ] = \@both;
73 1092 push @heap, [ $x->[0] + $y->[0], $x->[1] ];
74 }
75 19 ▶ return \@depth if max(@depth) <= 32;
Branch: 1 branch
BranchTrueFalseTotal
if &max(@depth) <= 32 19 0 19
76 }
77 0 die "no Huffman code within 32 bits\n";
78 }
79  
80 # The codewords, as the specification assigns them: [ value, length ] per
81 # entry, the value's bits read from the most significant.
82 20 ▶sub _codes ($lengths) {
Subroutine _codes: called CC=5 SCAR=16.8
83 20 my $root = {};
84 20 my @codes;
85 20 for my $e (0 .. $#$lengths) {
86 1119 my $length = $lengths->[$e];
87 1119 my $code = _take($root, $length, 0);
88 1119 ▶ die "codebook lengths overfill the code tree (entry $e)\n" if !defined $code;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $code 0 1119 1119
89 1119 push @codes, [ $code, $length ];
90 }
91 20 ▶ die "codebook lengths leave the code tree unfilled\n" if @$lengths > 1 && !$root->{full};
Branch: 1 branch
BranchTrueFalseTotal
if @$lengths > 1 and not $root->{"full"} 0 20 20
Condition33%1/3
@$lengths > 1 and not $root->{"full"}
!ll&&!rl&&r
0200
MC/DC0%0/2
@$lengths > 1 and not $root->{"full"}
@$lengths > 1 not $root->{"full"}
Truth table33%1/3
A and not(B)
A= @$lengths > 1B= not $root->{"full"}
ABresult
0X0
100
111
92 20 return \@codes;
93 }
94  
95 # The leftmost free place at $depth below $node: its value, or undef.
96 22207 ▶sub _take ($node, $depth, $value) {
Subroutine _take: called CC=13 SCAR=25.7
97 22207 ▶ return undef if $node->{full} || $node->{leaf};
Branch: 1 branch
BranchTrueFalseTotal
if $node->{"full"} or $node->{"leaf"} 7374 14833 22207
Condition66%2/3
$node->{"full"} or $node->{"leaf"}
l!l&&r!l&&!r
7374014833
MC/DC50%1/2
$node->{"full"} or $node->{"leaf"}
$node->{"full"} $node->{"leaf"}
Truth table66%2/3
A or B
A= $node->{"full"}B= $node->{"leaf"}
ABresult
1X1
011
000
98 14833 ▶ if ($depth == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth == 0) 1957 12876 14833
99 1957 ▶ return undef if $node->{0} || $node->{1}; # an inner node: taken below
Branch: 1 branch
BranchTrueFalseTotal
if $node->{0} or $node->{1} 838 1119 1957
Condition66%2/3
$node->{0} or $node->{1}
l!l&&r!l&&!r
83801119
MC/DC50%1/2
$node->{0} or $node->{1}
$node->{0} $node->{1}
Truth table66%2/3
A or B
A= $node->{0}B= $node->{1}
ABresult
1X1
011
000
100 1119 $node->{leaf} = $node->{full} = 1;
101 1119 return $value;
102 }
103 12876 for my $bit (0, 1) {
104 21088 ▶ my $child = $node->{$bit} //= {};
Condition100%2/2
$node->{$bit} //= {}
l!l
188902198
MC/DC100%1/1
$node->{$bit} //= {}
$node->{$bit}
Truth table100%2/2
A
A= $node->{$bit}
Aresult
11
00
105 21088 my $got = _take($child, $depth - 1, 2 * $value + $bit);
106 21088 ▶ if (defined $got) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $got) 10478 10610 21088
107 10478 ▶ $node->{full} = 1 if $node->{0} && $node->{0}{full} && $node->{1} && $node->{1}{full};
Branch: 1 branch
BranchTrueFalseTotal
if $node->{0} and $node->{0}{"full"} and $node->{1} and $node->{1}{"full"} 1099 9379 10478
Condition88%8/9
$node->{0} and $node->{0}{"full"} and $node->{1} and $node->{1}{"full"}
!ll&&!rl&&r
510042791099
$node->{0} and $node->{0}{"full"} and $node->{1}
!ll&&!rl&&r
42978035378
$node->{0} and $node->{0}{"full"}
!ll&&!rl&&r
042976181
MC/DC75%3/4
$node->{0} and $node->{0}{"full"} and $node->{1} and $node->{1}{"full"}
$node->{0} $node->{0}{"full"} $node->{1} $node->{1}{"full"}
Truth table80%4/5
A and B and C and D
A= $node->{0}B= $node->{0}{"full"}C= $node->{1}D= $node->{1}{"full"}
ABCDresult
0XXX0
10XX0
110X0
11100
11111
108 10478 return $got;
109 }
110 }
111 2398 return undef;
112 }
113  
114 # The values of an entry of a lattice book.
115 1 ▶sub vector ($self, $entry) {
Subroutine vector: called CC=2 SCAR=6.9
Pod documented
116 1 my @v;
117 1 my $div = 1;
118 1 for (1 .. $self->{dim}) {
119 2 push @v, $self->{minimum} + (int($entry / $div) % $self->{m}) * $self->{delta};
120 2 $div *= $self->{m};
121 }
122 1 return @v;
123 }
124  
125 # The entry of a lattice book whose values are these (each one of the
126 # book's values): value i is the entry's digit i, in base m.
127 8305 ▶sub entry ($self, @values) {
Subroutine entry: called CC=2 SCAR=6.9
Pod documented
128 8305 my ($entry, $mul) = (0, 1);
129 8305 for my $v (@values) {
130 18370 $entry += $mul * int(($v - $self->{minimum}) / $self->{delta} + 0.5);
131 18370 $mul *= $self->{m};
132 }
133 8305 return $entry;
134 }
135  
136 # Writes an entry's codeword: its bits from the most significant, into a
137 # writer that packs from the least significant (so the code goes reversed).
138 15540 ▶sub put ($self, $out, $entry) {
Subroutine put: called CC=3 SCAR=11.0
Pod documented
139 15540 ▶ $self->{counts}[$entry]++ if $self->{counts};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"counts"} 0 15540 15540
140 15540 my ($code, $length) = @{ $self->{codes}[$entry] };
141 15540 my $reversed = 0;
142 15540 for (1 .. $length) {
143 60792 $reversed = ($reversed << 1) | ($code & 1);
144 60792 $code >>= 1;
145 }
146 15540 $out->put($reversed, $length);
147 15540 return;
148 }
149  
150 # Counting the entries written from now on (for training the weights):
151 # the counts so far.
152 0 ▶sub count ($self) { return $self->{counts} //= [ (0) x $self->{entries} ] }
Subroutine count: not called CC=2 SCAR=17.9
Pod documented
Condition0%0/2
$self->{"counts"} //= [(0) x $self->{"entries"}]
l!l
00
MC/DC0%0/1
$self->{"counts"} //= [(0) x $self->{"entries"}]
$self->{"counts"}
Truth table0%0/2
A
A= $self->{"counts"}
Aresult
11
00
153  
154 # The bits of an entry's codeword.
155 0 ▶sub bits ($self, $entry) { return $self->{lengths}[$entry] }
Subroutine bits: not called CC=1 SCAR=6.9
Pod documented
156  
157 # The book in the setup header.
158 18 ▶sub header ($self, $out) {
Subroutine header: called CC=5 SCAR=16.1
Pod documented
159 18 $out->put(SYNC, 24);
160 18 $out->put($self->{dim}, 16);
161 18 $out->put($self->{entries}, 24);
162 18 $out->put(0, 1); # not ordered
163 18 $out->put(0, 1); # not sparse: every entry has a codeword
164 18 $out->put($_ - 1, 5) for @{ $self->{lengths} };
165  
166 18 ▶ if (!$self->{m}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->{"m"}) 4 14 18
167 4 $out->put(0, 4); # lookup type 0: no values
168 4 return;
169 }
170  
171 14 $out->put(1, 4); # lookup type 1: a lattice
172 14 $out->put(float32($self->{minimum}), 32);
173 14 $out->put(float32($self->{delta}), 32);
174 14 my $bits = 1;
175 14 ▶ $bits++ while (1 << $bits) < $self->{m};
Branch: 1 branch
BranchTrueFalseTotal
1 << $bits < $self->{"m"} and do { ++$bits } 36 14 50
176 14 $out->put($bits - 1, 4);
177 14 $out->put(0, 1); # values not cumulative
178 14 $out->put($_, $bits) for 0 .. $self->{m} - 1;
179 14 return;
180 }
181  
182 # Vorbis' float32: a sign, a 10-bit exponent and a 21-bit mantissa, read as
183 # mantissa * 2^(exponent - 788). Here the mantissa holds x * 2^(20 - e), so
184 # the exponent stored is e + 768.
185 33 ▶sub float32 ($x) {
Subroutine float32: called CC=6 SCAR=19.2
Pod documented
186 33 ▶ return 0 if $x == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $x == 0 0 33 33
187 33 ▶ my $sign = $x < 0 ? 0x80000000 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$x < 0 ? : 16 17 33
188 33 $x = abs $x;
189 33 my $exp = int(log($x) / log(2));
190 33 ▶ $exp-- while 2**$exp > $x;
Branch: 1 branch
BranchTrueFalseTotal
2 ** $exp > $x and do { --$exp } 0 33 33
191 33 ▶ $exp++ while 2**($exp + 1) <= $x;
Branch: 1 branch
BranchTrueFalseTotal
2 ** ($exp + 1) <= $x and do { ++$exp } 0 33 33
192 33 my $mantissa = int($x * 2**(20 - $exp) + 0.5);
193 0 ▶ if ($mantissa >= 1 << 21) { $mantissa >>= 1; $exp++ }
Branch: 1 branch
BranchTrueFalseTotal
if ($mantissa >= 2097152) 0 33 33
194 33 return $sign | (($exp + 768) << 21) | $mantissa;
195 }
196  
197 1 1;
198  
199 __END__
« lib/Peta/MIDI/Encoder.pm ↑ Summary lib/Peta/MIDI/Event.pm »