| 1 | package Net::Nostr::Negentropy; | ||||||||||||||||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||||||||||||||||
| 3 | 1 | ▶ | use strictures 2; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 4 | |||||||||||||||||||||||||||||||||||||||||||
| 5 | 1 | ▶ | use Net::Nostr::_ConstructorArgs (); | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||||||||||||||||||||
| 7 | 1 | ▶ | use Carp qw(croak); | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 8 | 1 | ▶ | use Digest::SHA qw(sha256); | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 9 | |||||||||||||||||||||||||||||||||||||||||||
| 10 | 1 | my $HEX64 = qr/\A[0-9a-f]{64}\z/; | |||||||||||||||||||||||||||||||||||||||||
| 11 | 1 | my $IDLIST_THRESHOLD = 48; | |||||||||||||||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||||||||||||||||
| 13 | 1 | ▶ | use constant INFINITY_TS => ~0; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||||||||||||||||
| 15 | 29 | ▶ | sub new { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
new: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 16 | 29 | my $class = shift; | |||||||||||||||||||||||||||||||||||||||||
| 17 | 29 | my %args = Net::Nostr::_ConstructorArgs::normalize(@_); | |||||||||||||||||||||||||||||||||||||||||
| 18 | 29 | my @unknown = grep { $_ ne 'frame_size_limit' } keys %args; | |||||||||||||||||||||||||||||||||||||||||
| 19 | 29 | ▶ | croak "unknown argument(s): " . join(', ', sort @unknown) if @unknown; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 20 | return bless { | ||||||||||||||||||||||||||||||||||||||||||
| 21 | _items => [], | ||||||||||||||||||||||||||||||||||||||||||
| 22 | _sealed => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 23 | _is_initiator => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 24 | 28 | ▶ | frame_size_limit => $args{frame_size_limit} // 0, | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%2/2
$args{"frame_size_limit"} // 0
MC/DC100%1/1
$args{"frame_size_limit"} // 0
$args{"frame_size_limit"}
Truth table100%2/2
A
A= $args{"frame_size_limit"}
| |||||||||||||||||||||||||||||||||||||||||||
| 25 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 26 | } | ||||||||||||||||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||||||||||||||||
| 28 | 234 | ▶ | sub add_item { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
add_item: called CC=8 SCAR=20.8
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 29 | 234 | my ($self, $timestamp, $id_hex) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 30 | 234 | ▶ | croak "cannot add items after sealed" if $self->{_sealed}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 31 | 233 | ▶ | croak "timestamp must be a non-negative integer" | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%6/6
defined $timestamp and $timestamp >= 0 and $timestamp == int $timestamp
defined $timestamp and $timestamp >= 0
MC/DC100%3/3
defined $timestamp and $timestamp >= 0 and $timestamp == int $timestamp
defined $timestamp
$timestamp >= 0
$timestamp == int $timestamp
Truth table100%4/4
A and B and C
A= defined $timestampB= $timestamp >= 0C= $timestamp == int $timestamp
| |||||||||||||||||||||||||||||||||||||||||||
| 32 | unless defined $timestamp && $timestamp >= 0 && $timestamp == int($timestamp); | ||||||||||||||||||||||||||||||||||||||||||
| 33 | 230 | ▶ | croak "timestamp must not be the reserved infinity value" | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 34 | if $timestamp == INFINITY_TS; | ||||||||||||||||||||||||||||||||||||||||||
| 35 | 229 | ▶ | croak "id must be 64-char lowercase hex" unless defined $id_hex && $id_hex =~ $HEX64; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
defined $id_hex and $id_hex =~ /$HEX64/
MC/DC100%2/2
defined $id_hex and $id_hex =~ /$HEX64/
defined $id_hex
$id_hex =~ /$HEX64/
Truth table100%3/3
A and B
A= defined $id_hexB= $id_hex =~ /$HEX64/
| |||||||||||||||||||||||||||||||||||||||||||
| 36 | 225 | push @{$self->{_items}}, [$timestamp, pack('H*', $id_hex)]; | |||||||||||||||||||||||||||||||||||||||||
| 37 | } | ||||||||||||||||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||||||||||||||||
| 39 | 15 | ▶ | sub seal { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
seal: called CC=2 SCAR=7.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 40 | 15 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 41 | $self->{_items} = [ | ||||||||||||||||||||||||||||||||||||||||||
| 42 | 15 | ▶ | sort { $a->[0] <=> $b->[0] || $a->[1] cmp $b->[1] } @{$self->{_items}} | ||||||||||||||||||||||||||||||||||||||||
|
Condition66%2/3
$Net::Nostr::Negentropy::a->[0] <=> $Net::Nostr::Negentropy::b->[0] || $Net::Nostr::Negentropy::a->[1] cmp $Net::Nostr::Negentropy::b->[1]
MC/DC0%0/2
$Net::Nostr::Negentropy::a->[0] <=> $Net::Nostr::Negentropy::b->[0] || $Net::Nostr::Negentropy::a->[1] cmp $Net::Nostr::Negentropy::b->[1]
$Net::Nostr::Negentropy::a->[0] <=> $Net::Nostr::Negentropy::b->[0]
$Net::Nostr::Negentropy::a->[1] cmp $Net::Nostr::Negentropy::b->[1]
Truth table66%2/3
A || B
A= $Net::Nostr::Negentropy::a->[0] <=> $Net::Nostr::Negentropy::b->[0]B= $Net::Nostr::Negentropy::a->[1] cmp $Net::Nostr::Negentropy::b->[1]
| |||||||||||||||||||||||||||||||||||||||||||
| 43 | ]; | ||||||||||||||||||||||||||||||||||||||||||
| 44 | 15 | $self->{_sealed} = 1; | |||||||||||||||||||||||||||||||||||||||||
| 45 | } | ||||||||||||||||||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||||||||||||||||
| 47 | 8 | ▶ | sub initiate { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
initiate: called CC=7 SCAR=19.5
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 48 | 8 | my ($self) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 49 | 8 | ▶ | croak "must seal before initiate" unless $self->{_sealed}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 50 | 7 | $self->{_is_initiator} = 1; | |||||||||||||||||||||||||||||||||||||||||
| 51 | |||||||||||||||||||||||||||||||||||||||||||
| 52 | 7 | my @items = @{$self->{_items}}; | |||||||||||||||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||||||||||||||||
| 54 | 7 | my @ranges; | |||||||||||||||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||||||||||||||||
| 56 | 7 | ▶ | if (@items <= $IDLIST_THRESHOLD) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 57 | push @ranges, { | ||||||||||||||||||||||||||||||||||||||||||
| 58 | upper => [INFINITY_TS, ''], | ||||||||||||||||||||||||||||||||||||||||||
| 59 | mode => 2, | ||||||||||||||||||||||||||||||||||||||||||
| 60 | 6 | payload => [map { $_->[1] } @items], | |||||||||||||||||||||||||||||||||||||||||
| 61 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 62 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 63 | 1 | my $n_ranges = int(sqrt(@items)); | |||||||||||||||||||||||||||||||||||||||||
| 64 | 1 | ▶ | $n_ranges = 2 if $n_ranges < 2; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 65 | 1 | my $per_range = int(@items / $n_ranges); | |||||||||||||||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||||||||||||||||
| 67 | 1 | for my $i (0 .. $n_ranges - 1) { | |||||||||||||||||||||||||||||||||||||||||
| 68 | 10 | my $start = $i * $per_range; | |||||||||||||||||||||||||||||||||||||||||
| 69 | 10 | ▶ | my $end = ($i == $n_ranges - 1) ? $#items : ($start + $per_range - 1); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 70 | 10 | my @range_items = @items[$start .. $end]; | |||||||||||||||||||||||||||||||||||||||||
| 71 | |||||||||||||||||||||||||||||||||||||||||||
| 72 | 10 | my $upper; | |||||||||||||||||||||||||||||||||||||||||
| 73 | 10 | ▶ | if ($i == $n_ranges - 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 74 | 1 | $upper = [INFINITY_TS, '']; | |||||||||||||||||||||||||||||||||||||||||
| 75 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 76 | 9 | $upper = _compute_bound($items[$end], $items[$end + 1]); | |||||||||||||||||||||||||||||||||||||||||
| 77 | } | ||||||||||||||||||||||||||||||||||||||||||
| 78 | |||||||||||||||||||||||||||||||||||||||||||
| 79 | 10 | push @ranges, { | |||||||||||||||||||||||||||||||||||||||||
| 80 | upper => $upper, | ||||||||||||||||||||||||||||||||||||||||||
| 81 | mode => 1, | ||||||||||||||||||||||||||||||||||||||||||
| 82 | payload => _fingerprint(@range_items), | ||||||||||||||||||||||||||||||||||||||||||
| 83 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 84 | } | ||||||||||||||||||||||||||||||||||||||||||
| 85 | } | ||||||||||||||||||||||||||||||||||||||||||
| 86 | |||||||||||||||||||||||||||||||||||||||||||
| 87 | 7 | my $msg = _encode_message(\@ranges); | |||||||||||||||||||||||||||||||||||||||||
| 88 | 7 | $self->_check_frame_size_limit($msg, 'initiate'); | |||||||||||||||||||||||||||||||||||||||||
| 89 | 6 | return unpack('H*', $msg); | |||||||||||||||||||||||||||||||||||||||||
| 90 | } | ||||||||||||||||||||||||||||||||||||||||||
| 91 | |||||||||||||||||||||||||||||||||||||||||||
| 92 | 10 | ▶ | sub reconcile { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
reconcile: called CC=14 SCAR=26.4
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 93 | 10 | my ($self, $hex_msg) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 94 | 10 | ▶ | croak "must seal before reconcile" unless $self->{_sealed}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 95 | |||||||||||||||||||||||||||||||||||||||||||
| 96 | 9 | my $msg_bytes = pack('H*', $hex_msg); | |||||||||||||||||||||||||||||||||||||||||
| 97 | 9 | $self->_check_frame_size_limit($msg_bytes, 'reconcile input'); | |||||||||||||||||||||||||||||||||||||||||
| 98 | 8 | my $ranges = _decode_message($msg_bytes); | |||||||||||||||||||||||||||||||||||||||||
| 99 | |||||||||||||||||||||||||||||||||||||||||||
| 100 | 6 | my @items = @{$self->{_items}}; | |||||||||||||||||||||||||||||||||||||||||
| 101 | 6 | my @response_ranges; | |||||||||||||||||||||||||||||||||||||||||
| 102 | my @have_ids; | ||||||||||||||||||||||||||||||||||||||||||
| 103 | 6 | my @need_ids; | |||||||||||||||||||||||||||||||||||||||||
| 104 | |||||||||||||||||||||||||||||||||||||||||||
| 105 | 6 | my $lower = [0, '']; | |||||||||||||||||||||||||||||||||||||||||
| 106 | 6 | my $have_non_skip = 0; | |||||||||||||||||||||||||||||||||||||||||
| 107 | |||||||||||||||||||||||||||||||||||||||||||
| 108 | 6 | for my $range (@$ranges) { | |||||||||||||||||||||||||||||||||||||||||
| 109 | 24 | my $upper = $range->{upper}; | |||||||||||||||||||||||||||||||||||||||||
| 110 | 24 | my @local = _items_in_range(\@items, $lower, $upper); | |||||||||||||||||||||||||||||||||||||||||
| 111 | |||||||||||||||||||||||||||||||||||||||||||
| 112 | 24 | ▶ | if ($range->{mode} == 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 3 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 113 | 9 | push @response_ranges, { upper => $upper, mode => 0, payload => undef }; | |||||||||||||||||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||||||||||||||||
| 115 | elsif ($range->{mode} == 1) { | ||||||||||||||||||||||||||||||||||||||||||
| 116 | 10 | my $local_fp = _fingerprint(@local); | |||||||||||||||||||||||||||||||||||||||||
| 117 | 10 | ▶ | if ($local_fp eq $range->{payload}) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 118 | 9 | push @response_ranges, { upper => $upper, mode => 0, payload => undef }; | |||||||||||||||||||||||||||||||||||||||||
| 119 | } | ||||||||||||||||||||||||||||||||||||||||||
| 120 | elsif (@local <= $IDLIST_THRESHOLD) { | ||||||||||||||||||||||||||||||||||||||||||
| 121 | push @response_ranges, { | ||||||||||||||||||||||||||||||||||||||||||
| 122 | upper => $upper, | ||||||||||||||||||||||||||||||||||||||||||
| 123 | mode => 2, | ||||||||||||||||||||||||||||||||||||||||||
| 124 | 1 | payload => [map { $_->[1] } @local], | |||||||||||||||||||||||||||||||||||||||||
| 125 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 126 | 1 | $have_non_skip = 1; | |||||||||||||||||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||||||||||||||||
| 128 | else { | ||||||||||||||||||||||||||||||||||||||||||
| 129 | 0 | push @response_ranges, _split_items_into_ranges(\@local, $upper); | |||||||||||||||||||||||||||||||||||||||||
| 130 | 0 | $have_non_skip = 1; | |||||||||||||||||||||||||||||||||||||||||
| 131 | } | ||||||||||||||||||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||||||||||||||||
| 133 | elsif ($range->{mode} == 2) { | ||||||||||||||||||||||||||||||||||||||||||
| 134 | 5 | my %their_ids = map { $_ => 1 } @{$range->{payload}}; | |||||||||||||||||||||||||||||||||||||||||
| 135 | 5 | my %our_ids = map { $_->[1] => 1 } @local; | |||||||||||||||||||||||||||||||||||||||||
| 136 | |||||||||||||||||||||||||||||||||||||||||||
| 137 | 5 | for my $id (@{$range->{payload}}) { | |||||||||||||||||||||||||||||||||||||||||
| 138 | 25 | ▶ | push @need_ids, unpack('H*', $id) unless $our_ids{$id}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||||||||||||||||
| 140 | 5 | for my $item (@local) { | |||||||||||||||||||||||||||||||||||||||||
| 141 | 25 | ▶ | push @have_ids, unpack('H*', $item->[1]) unless $their_ids{$item->[1]}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 142 | } | ||||||||||||||||||||||||||||||||||||||||||
| 143 | |||||||||||||||||||||||||||||||||||||||||||
| 144 | 5 | ▶ | if ($self->{_is_initiator}) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 145 | 3 | push @response_ranges, { upper => $upper, mode => 0, payload => undef }; | |||||||||||||||||||||||||||||||||||||||||
| 146 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 147 | push @response_ranges, { | ||||||||||||||||||||||||||||||||||||||||||
| 148 | upper => $upper, | ||||||||||||||||||||||||||||||||||||||||||
| 149 | mode => 2, | ||||||||||||||||||||||||||||||||||||||||||
| 150 | 2 | payload => [map { $_->[1] } @local], | |||||||||||||||||||||||||||||||||||||||||
| 151 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 152 | 2 | $have_non_skip = 1; | |||||||||||||||||||||||||||||||||||||||||
| 153 | } | ||||||||||||||||||||||||||||||||||||||||||
| 154 | } | ||||||||||||||||||||||||||||||||||||||||||
| 155 | |||||||||||||||||||||||||||||||||||||||||||
| 156 | 24 | $lower = $upper; | |||||||||||||||||||||||||||||||||||||||||
| 157 | } | ||||||||||||||||||||||||||||||||||||||||||
| 158 | |||||||||||||||||||||||||||||||||||||||||||
| 159 | 6 | my $response_hex; | |||||||||||||||||||||||||||||||||||||||||
| 160 | 6 | ▶ | if ($have_non_skip) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 161 | 3 | my $response_bytes = _encode_message(\@response_ranges); | |||||||||||||||||||||||||||||||||||||||||
| 162 | 3 | $self->_check_frame_size_limit($response_bytes, 'reconcile response'); | |||||||||||||||||||||||||||||||||||||||||
| 163 | 3 | $response_hex = unpack('H*', $response_bytes); | |||||||||||||||||||||||||||||||||||||||||
| 164 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 165 | 3 | $response_hex = undef; | |||||||||||||||||||||||||||||||||||||||||
| 166 | } | ||||||||||||||||||||||||||||||||||||||||||
| 167 | |||||||||||||||||||||||||||||||||||||||||||
| 168 | 6 | return ($response_hex, \@have_ids, \@need_ids); | |||||||||||||||||||||||||||||||||||||||||
| 169 | } | ||||||||||||||||||||||||||||||||||||||||||
| 170 | |||||||||||||||||||||||||||||||||||||||||||
| 171 | 19 | ▶ | sub _check_frame_size_limit { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_check_frame_size_limit: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||||||||||||||||
| 172 | 19 | my ($self, $bytes, $context) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 173 | |||||||||||||||||||||||||||||||||||||||||||
| 174 | 19 | ▶ | return unless $self->{frame_size_limit}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 175 | 2 | ▶ | return if length($bytes) <= $self->{frame_size_limit}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 176 | |||||||||||||||||||||||||||||||||||||||||||
| 177 | croak "frame_size_limit exceeded for $context: " | ||||||||||||||||||||||||||||||||||||||||||
| 178 | 2 | . length($bytes) . " bytes > " . $self->{frame_size_limit} . " bytes"; | |||||||||||||||||||||||||||||||||||||||||
| 179 | } | ||||||||||||||||||||||||||||||||||||||||||
| 180 | |||||||||||||||||||||||||||||||||||||||||||
| 181 | # --- Binary protocol internals --- | ||||||||||||||||||||||||||||||||||||||||||
| 182 | |||||||||||||||||||||||||||||||||||||||||||
| 183 | 113 | ▶ | sub _encode_varint { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_encode_varint: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||||||||||||||||
| 184 | 113 | my ($n) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 185 | 113 | my @bytes; | |||||||||||||||||||||||||||||||||||||||||
| 186 | 113 | ▶ | do { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 187 | 113 | unshift @bytes, $n & 0x7f; | |||||||||||||||||||||||||||||||||||||||||
| 188 | 113 | $n >>= 7; | |||||||||||||||||||||||||||||||||||||||||
| 189 | } while ($n > 0); | ||||||||||||||||||||||||||||||||||||||||||
| 190 | 113 | $bytes[$_] |= 0x80 for 0 .. $#bytes - 1; | |||||||||||||||||||||||||||||||||||||||||
| 191 | 113 | return pack('C*', @bytes); | |||||||||||||||||||||||||||||||||||||||||
| 192 | } | ||||||||||||||||||||||||||||||||||||||||||
| 193 | |||||||||||||||||||||||||||||||||||||||||||
| 194 | 77 | ▶ | sub _decode_varint { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_decode_varint: called CC=3 SCAR=11.1
| |||||||||||||||||||||||||||||||||||||||||||
| 195 | 77 | my ($buf, $pos) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 196 | 77 | my $n = 0; | |||||||||||||||||||||||||||||||||||||||||
| 197 | 77 | while (1) { | |||||||||||||||||||||||||||||||||||||||||
| 198 | 77 | ▶ | croak "varint: unexpected end of buffer" if $pos >= length($buf); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 199 | 77 | my $byte = ord(substr($buf, $pos++, 1)); | |||||||||||||||||||||||||||||||||||||||||
| 200 | 77 | $n = ($n << 7) | ($byte & 0x7f); | |||||||||||||||||||||||||||||||||||||||||
| 201 | 77 | ▶ | last unless $byte & 0x80; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 202 | } | ||||||||||||||||||||||||||||||||||||||||||
| 203 | 77 | return ($n, $pos); | |||||||||||||||||||||||||||||||||||||||||
| 204 | } | ||||||||||||||||||||||||||||||||||||||||||
| 205 | |||||||||||||||||||||||||||||||||||||||||||
| 206 | 10 | ▶ | sub _encode_message { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_encode_message: called CC=7 SCAR=19.5
| |||||||||||||||||||||||||||||||||||||||||||
| 207 | 10 | my ($ranges) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 208 | 10 | my $msg = chr(0x61); | |||||||||||||||||||||||||||||||||||||||||
| 209 | 10 | my $prev_ts = 0; | |||||||||||||||||||||||||||||||||||||||||
| 210 | 10 | for my $range (@$ranges) { | |||||||||||||||||||||||||||||||||||||||||
| 211 | 28 | my ($ts, $prefix) = @{$range->{upper}}; | |||||||||||||||||||||||||||||||||||||||||
| 212 | |||||||||||||||||||||||||||||||||||||||||||
| 213 | # Encode bound | ||||||||||||||||||||||||||||||||||||||||||
| 214 | 28 | my $encoded_ts; | |||||||||||||||||||||||||||||||||||||||||
| 215 | 28 | ▶ | if ($ts == INFINITY_TS) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 216 | 10 | $encoded_ts = 0; | |||||||||||||||||||||||||||||||||||||||||
| 217 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 218 | 18 | $encoded_ts = 1 + ($ts - $prev_ts); | |||||||||||||||||||||||||||||||||||||||||
| 219 | } | ||||||||||||||||||||||||||||||||||||||||||
| 220 | 28 | $msg .= _encode_varint($encoded_ts); | |||||||||||||||||||||||||||||||||||||||||
| 221 | 28 | $msg .= _encode_varint(length($prefix)); | |||||||||||||||||||||||||||||||||||||||||
| 222 | 28 | $msg .= $prefix; | |||||||||||||||||||||||||||||||||||||||||
| 223 | |||||||||||||||||||||||||||||||||||||||||||
| 224 | # Encode mode + payload | ||||||||||||||||||||||||||||||||||||||||||
| 225 | 28 | $msg .= _encode_varint($range->{mode}); | |||||||||||||||||||||||||||||||||||||||||
| 226 | 28 | ▶ | if ($range->{mode} == 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 227 | 10 | $msg .= $range->{payload}; | |||||||||||||||||||||||||||||||||||||||||
| 228 | } elsif ($range->{mode} == 2) { | ||||||||||||||||||||||||||||||||||||||||||
| 229 | 9 | my @ids = @{$range->{payload}}; | |||||||||||||||||||||||||||||||||||||||||
| 230 | 9 | $msg .= _encode_varint(scalar @ids); | |||||||||||||||||||||||||||||||||||||||||
| 231 | 9 | $msg .= $_ for @ids; | |||||||||||||||||||||||||||||||||||||||||
| 232 | } | ||||||||||||||||||||||||||||||||||||||||||
| 233 | |||||||||||||||||||||||||||||||||||||||||||
| 234 | 28 | ▶ | $prev_ts = $ts unless $ts == INFINITY_TS; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 235 | } | ||||||||||||||||||||||||||||||||||||||||||
| 236 | 10 | return $msg; | |||||||||||||||||||||||||||||||||||||||||
| 237 | } | ||||||||||||||||||||||||||||||||||||||||||
| 238 | |||||||||||||||||||||||||||||||||||||||||||
| 239 | 8 | ▶ | sub _decode_message { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_decode_message: called CC=13 SCAR=25.7
| |||||||||||||||||||||||||||||||||||||||||||
| 240 | 8 | my ($buf) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 241 | 8 | ▶ | croak "empty message" unless length $buf; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 242 | 7 | my $version = ord(substr($buf, 0, 1)); | |||||||||||||||||||||||||||||||||||||||||
| 243 | 7 | ▶ | croak "unsupported negentropy protocol version: $version" | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 244 | unless $version == 0x61; | ||||||||||||||||||||||||||||||||||||||||||
| 245 | |||||||||||||||||||||||||||||||||||||||||||
| 246 | 6 | my @ranges; | |||||||||||||||||||||||||||||||||||||||||
| 247 | 6 | my $pos = 1; | |||||||||||||||||||||||||||||||||||||||||
| 248 | 6 | my $prev_ts = 0; | |||||||||||||||||||||||||||||||||||||||||
| 249 | |||||||||||||||||||||||||||||||||||||||||||
| 250 | 6 | ▶ | while ($pos < length $buf) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 251 | # Decode bound | ||||||||||||||||||||||||||||||||||||||||||
| 252 | 24 | my ($encoded_ts, $pos2) = _decode_varint($buf, $pos); | |||||||||||||||||||||||||||||||||||||||||
| 253 | 24 | my $ts; | |||||||||||||||||||||||||||||||||||||||||
| 254 | 24 | ▶ | if ($encoded_ts == 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 255 | 6 | $ts = INFINITY_TS; | |||||||||||||||||||||||||||||||||||||||||
| 256 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 257 | 18 | $ts = $prev_ts + $encoded_ts - 1; | |||||||||||||||||||||||||||||||||||||||||
| 258 | } | ||||||||||||||||||||||||||||||||||||||||||
| 259 | 24 | my ($prefix_len, $pos3) = _decode_varint($buf, $pos2); | |||||||||||||||||||||||||||||||||||||||||
| 260 | 24 | ▶ | croak "truncated bound prefix" | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 261 | if $pos3 + $prefix_len > length($buf); | ||||||||||||||||||||||||||||||||||||||||||
| 262 | 24 | my $prefix = substr($buf, $pos3, $prefix_len); | |||||||||||||||||||||||||||||||||||||||||
| 263 | 24 | $pos = $pos3 + $prefix_len; | |||||||||||||||||||||||||||||||||||||||||
| 264 | |||||||||||||||||||||||||||||||||||||||||||
| 265 | # Decode mode | ||||||||||||||||||||||||||||||||||||||||||
| 266 | 24 | my ($mode, $pos4) = _decode_varint($buf, $pos); | |||||||||||||||||||||||||||||||||||||||||
| 267 | 24 | $pos = $pos4; | |||||||||||||||||||||||||||||||||||||||||
| 268 | |||||||||||||||||||||||||||||||||||||||||||
| 269 | 24 | my $payload; | |||||||||||||||||||||||||||||||||||||||||
| 270 | 24 | ▶ | if ($mode == 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 3 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 271 | 9 | $payload = undef; | |||||||||||||||||||||||||||||||||||||||||
| 272 | } elsif ($mode == 1) { | ||||||||||||||||||||||||||||||||||||||||||
| 273 | 10 | ▶ | croak "truncated fingerprint: expected 16 bytes" | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 274 | if $pos + 16 > length($buf); | ||||||||||||||||||||||||||||||||||||||||||
| 275 | 10 | $payload = substr($buf, $pos, 16); | |||||||||||||||||||||||||||||||||||||||||
| 276 | 10 | $pos += 16; | |||||||||||||||||||||||||||||||||||||||||
| 277 | } elsif ($mode == 2) { | ||||||||||||||||||||||||||||||||||||||||||
| 278 | 5 | my ($count, $pos5) = _decode_varint($buf, $pos); | |||||||||||||||||||||||||||||||||||||||||
| 279 | 5 | $pos = $pos5; | |||||||||||||||||||||||||||||||||||||||||
| 280 | 5 | ▶ | croak "truncated id list: expected " . ($count * 32) . " bytes" | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 281 | if $pos + ($count * 32) > length($buf); | ||||||||||||||||||||||||||||||||||||||||||
| 282 | 5 | my @ids; | |||||||||||||||||||||||||||||||||||||||||
| 283 | 5 | for (1 .. $count) { | |||||||||||||||||||||||||||||||||||||||||
| 284 | 25 | push @ids, substr($buf, $pos, 32); | |||||||||||||||||||||||||||||||||||||||||
| 285 | 25 | $pos += 32; | |||||||||||||||||||||||||||||||||||||||||
| 286 | } | ||||||||||||||||||||||||||||||||||||||||||
| 287 | 5 | $payload = \@ids; | |||||||||||||||||||||||||||||||||||||||||
| 288 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 289 | 0 | croak "unknown range mode: $mode"; | |||||||||||||||||||||||||||||||||||||||||
| 290 | } | ||||||||||||||||||||||||||||||||||||||||||
| 291 | |||||||||||||||||||||||||||||||||||||||||||
| 292 | 24 | push @ranges, { | |||||||||||||||||||||||||||||||||||||||||
| 293 | upper => [$ts, $prefix], | ||||||||||||||||||||||||||||||||||||||||||
| 294 | mode => $mode, | ||||||||||||||||||||||||||||||||||||||||||
| 295 | payload => $payload, | ||||||||||||||||||||||||||||||||||||||||||
| 296 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 297 | |||||||||||||||||||||||||||||||||||||||||||
| 298 | 24 | ▶ | $prev_ts = $ts unless $ts == INFINITY_TS; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 299 | } | ||||||||||||||||||||||||||||||||||||||||||
| 300 | |||||||||||||||||||||||||||||||||||||||||||
| 301 | 6 | return \@ranges; | |||||||||||||||||||||||||||||||||||||||||
| 302 | } | ||||||||||||||||||||||||||||||||||||||||||
| 303 | |||||||||||||||||||||||||||||||||||||||||||
| 304 | 20 | ▶ | sub _fingerprint { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_fingerprint: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||||||||||||||||
| 305 | 20 | my (@items) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 306 | 20 | my @sum = (0) x 32; | |||||||||||||||||||||||||||||||||||||||||
| 307 | 20 | for my $item (@items) { | |||||||||||||||||||||||||||||||||||||||||
| 308 | 202 | my @id = unpack('C*', $item->[1]); | |||||||||||||||||||||||||||||||||||||||||
| 309 | 202 | my $carry = 0; | |||||||||||||||||||||||||||||||||||||||||
| 310 | 202 | for my $i (0 .. 31) { | |||||||||||||||||||||||||||||||||||||||||
| 311 | 6464 | my $s = $sum[$i] + $id[$i] + $carry; | |||||||||||||||||||||||||||||||||||||||||
| 312 | 6464 | $sum[$i] = $s & 0xFF; | |||||||||||||||||||||||||||||||||||||||||
| 313 | 6464 | $carry = $s >> 8; | |||||||||||||||||||||||||||||||||||||||||
| 314 | } | ||||||||||||||||||||||||||||||||||||||||||
| 315 | } | ||||||||||||||||||||||||||||||||||||||||||
| 316 | 20 | my $sum_bytes = pack('C*', @sum); | |||||||||||||||||||||||||||||||||||||||||
| 317 | 20 | my $data = $sum_bytes . _encode_varint(scalar @items); | |||||||||||||||||||||||||||||||||||||||||
| 318 | 20 | return substr(sha256($data), 0, 16); | |||||||||||||||||||||||||||||||||||||||||
| 319 | } | ||||||||||||||||||||||||||||||||||||||||||
| 320 | |||||||||||||||||||||||||||||||||||||||||||
| 321 | 9 | ▶ | sub _compute_bound { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_compute_bound: called CC=4 SCAR=22.9
| |||||||||||||||||||||||||||||||||||||||||||
| 322 | 9 | my ($item_a, $item_b) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 323 | 9 | ▶ | if ($item_a->[0] != $item_b->[0]) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 324 | 9 | return [$item_b->[0], '']; | |||||||||||||||||||||||||||||||||||||||||
| 325 | } | ||||||||||||||||||||||||||||||||||||||||||
| 326 | 0 | my $len = 0; | |||||||||||||||||||||||||||||||||||||||||
| 327 | 0 | ▶ | while ($len < 32 && substr($item_a->[1], $len, 1) eq substr($item_b->[1], $len, 1)) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
$len < 32 and substr($item_a->[1], $len, 1) eq substr($item_b->[1], $len, 1)
MC/DC0%0/2
$len < 32 and substr($item_a->[1], $len, 1) eq substr($item_b->[1], $len, 1)
$len < 32
substr($item_a->[1], $len, 1) eq substr($item_b->[1], $len, 1)
Truth table0%0/3
A and B
A= $len < 32B= substr($item_a->[1], $len, 1) eq substr($item_b->[1], $len, 1)
| |||||||||||||||||||||||||||||||||||||||||||
| 328 | 0 | $len++; | |||||||||||||||||||||||||||||||||||||||||
| 329 | } | ||||||||||||||||||||||||||||||||||||||||||
| 330 | 0 | return [$item_b->[0], substr($item_b->[1], 0, $len + 1)]; | |||||||||||||||||||||||||||||||||||||||||
| 331 | } | ||||||||||||||||||||||||||||||||||||||||||
| 332 | |||||||||||||||||||||||||||||||||||||||||||
| 333 | 24 | ▶ | sub _items_in_range { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_items_in_range: called CC=4 SCAR=13.9
| |||||||||||||||||||||||||||||||||||||||||||
| 334 | 24 | my ($items, $lower, $upper) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 335 | 24 | my @result; | |||||||||||||||||||||||||||||||||||||||||
| 336 | 24 | for my $item (@$items) { | |||||||||||||||||||||||||||||||||||||||||
| 337 | 1134 | ▶ | next unless _item_ge_bound($item, $lower); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 338 | 234 | ▶ | last if !_item_lt_bound($item, $upper); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 339 | 216 | push @result, $item; | |||||||||||||||||||||||||||||||||||||||||
| 340 | } | ||||||||||||||||||||||||||||||||||||||||||
| 341 | 24 | return @result; | |||||||||||||||||||||||||||||||||||||||||
| 342 | } | ||||||||||||||||||||||||||||||||||||||||||
| 343 | |||||||||||||||||||||||||||||||||||||||||||
| 344 | 1134 | ▶ | sub _item_ge_bound { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_item_ge_bound: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||||||||||||||||
| 345 | 1134 | my ($item, $bound) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 346 | 1134 | my ($bts, $bprefix) = @$bound; | |||||||||||||||||||||||||||||||||||||||||
| 347 | 1134 | ▶ | return 1 if $item->[0] > $bts; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 348 | 918 | ▶ | return 0 if $item->[0] < $bts; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 349 | 18 | my $padded = $bprefix . ("\x00" x (32 - length($bprefix))); | |||||||||||||||||||||||||||||||||||||||||
| 350 | 18 | return $item->[1] ge $padded; | |||||||||||||||||||||||||||||||||||||||||
| 351 | } | ||||||||||||||||||||||||||||||||||||||||||
| 352 | |||||||||||||||||||||||||||||||||||||||||||
| 353 | 234 | ▶ | sub _item_lt_bound { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_item_lt_bound: called CC=4 SCAR=13.9
| |||||||||||||||||||||||||||||||||||||||||||
| 354 | 234 | my ($item, $bound) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 355 | 234 | my ($bts, $bprefix) = @$bound; | |||||||||||||||||||||||||||||||||||||||||
| 356 | 234 | ▶ | return 1 if $bts == INFINITY_TS; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 357 | 198 | ▶ | return 1 if $item->[0] < $bts; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 358 | 18 | ▶ | return 0 if $item->[0] > $bts; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 359 | 18 | my $padded = $bprefix . ("\x00" x (32 - length($bprefix))); | |||||||||||||||||||||||||||||||||||||||||
| 360 | 18 | return $item->[1] lt $padded; | |||||||||||||||||||||||||||||||||||||||||
| 361 | } | ||||||||||||||||||||||||||||||||||||||||||
| 362 | |||||||||||||||||||||||||||||||||||||||||||
| 363 | 0 | ▶ | sub _split_items_into_ranges { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_split_items_into_ranges: not called CC=5 SCAR=34.0
| |||||||||||||||||||||||||||||||||||||||||||
| 364 | 0 | my ($items, $final_upper) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 365 | 0 | my $n = int(sqrt(scalar @$items)); | |||||||||||||||||||||||||||||||||||||||||
| 366 | 0 | ▶ | $n = 2 if $n < 2; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 367 | 0 | my $per = int(@$items / $n); | |||||||||||||||||||||||||||||||||||||||||
| 368 | |||||||||||||||||||||||||||||||||||||||||||
| 369 | 0 | my @ranges; | |||||||||||||||||||||||||||||||||||||||||
| 370 | 0 | for my $i (0 .. $n - 1) { | |||||||||||||||||||||||||||||||||||||||||
| 371 | 0 | my $start = $i * $per; | |||||||||||||||||||||||||||||||||||||||||
| 372 | 0 | ▶ | my $end = ($i == $n - 1) ? $#{$items} : ($start + $per - 1); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 373 | 0 | my @sub = @{$items}[$start .. $end]; | |||||||||||||||||||||||||||||||||||||||||
| 374 | |||||||||||||||||||||||||||||||||||||||||||
| 375 | 0 | my $upper; | |||||||||||||||||||||||||||||||||||||||||
| 376 | 0 | ▶ | if ($i == $n - 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 377 | 0 | $upper = $final_upper; | |||||||||||||||||||||||||||||||||||||||||
| 378 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 379 | 0 | $upper = _compute_bound($items->[$end], $items->[$end + 1]); | |||||||||||||||||||||||||||||||||||||||||
| 380 | } | ||||||||||||||||||||||||||||||||||||||||||
| 381 | |||||||||||||||||||||||||||||||||||||||||||
| 382 | 0 | push @ranges, { | |||||||||||||||||||||||||||||||||||||||||
| 383 | upper => $upper, | ||||||||||||||||||||||||||||||||||||||||||
| 384 | mode => 1, | ||||||||||||||||||||||||||||||||||||||||||
| 385 | payload => _fingerprint(@sub), | ||||||||||||||||||||||||||||||||||||||||||
| 386 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 387 | } | ||||||||||||||||||||||||||||||||||||||||||
| 388 | 0 | return @ranges; | |||||||||||||||||||||||||||||||||||||||||
| 389 | } | ||||||||||||||||||||||||||||||||||||||||||
| 390 | |||||||||||||||||||||||||||||||||||||||||||
| 391 | 1 | 1; | |||||||||||||||||||||||||||||||||||||||||
| 392 | |||||||||||||||||||||||||||||||||||||||||||
| 393 | __END__ | ||||||||||||||||||||||||||||||||||||||||||