1 // Copyright 2024 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_allocator/fragmentation.h"
16
17 #include <cmath>
18
19 namespace pw::allocator {
20 namespace {
21
22 /// Adds the second number to the first, and return whether it overflowed.
AddTo(size_t & accumulate,size_t value)23 size_t AddTo(size_t& accumulate, size_t value) {
24 accumulate += value;
25 return accumulate < value ? 1 : 0;
26 }
27
28 } // namespace
29
AddFragment(size_t size)30 void Fragmentation::AddFragment(size_t size) {
31 constexpr size_t kShift = sizeof(size_t) * 4;
32 constexpr size_t kMask = (size_t(1) << kShift) - 1;
33 size_t hi = size >> kShift;
34 size_t lo = size & kMask;
35 size_t crossterm = hi * lo;
36 hi = hi * hi;
37 lo = lo * lo;
38 hi += (AddTo(crossterm, crossterm)) << kShift;
39 hi += (crossterm >> kShift) + AddTo(lo, (crossterm & kMask) << kShift);
40 hi += AddTo(sum_of_squares.lo, lo);
41 sum_of_squares.hi += hi;
42 sum += size;
43 }
44
CalculateFragmentation(const Fragmentation & fragmentation)45 float CalculateFragmentation(const Fragmentation& fragmentation) {
46 float sum_of_squares = fragmentation.sum_of_squares.hi;
47 if (sum_of_squares != 0) {
48 sum_of_squares *= std::pow(2.f, sizeof(size_t) * 8.f);
49 }
50 sum_of_squares += fragmentation.sum_of_squares.lo;
51 return 1.f - (std::sqrt(sum_of_squares) / fragmentation.sum);
52 }
53
54 } // namespace pw::allocator
55