Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 2cdf6020e3ff
Choose a base ref
...
head repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 441f4a434c34
Choose a head ref
  • 5 commits
  • 7 files changed
  • 1 contributor

Commits on Jul 9, 2020

  1. Bit operations.

    pleroy committed Jul 9, 2020
    Copy the full SHA
    f7b4f55 View commit details
  2. End of file.

    pleroy committed Jul 9, 2020
    Copy the full SHA
    f832377 View commit details
  3. After egg's review.

    pleroy committed Jul 9, 2020
    Copy the full SHA
    cd5147a View commit details
  4. Compilation error.

    pleroy committed Jul 9, 2020
    Copy the full SHA
    af798b7 View commit details
  5. Merge pull request #2635 from pleroy/Bits

    Move a few bit-related operations to a common place
    pleroy authored Jul 9, 2020
    Copy the full SHA
    441f4a4 View commit details
Showing with 88 additions and 23 deletions.
  1. +3 −0 base/base.vcxproj
  2. +9 −0 base/base.vcxproj.filters
  3. +3 −7 base/base32768_body.hpp
  4. +16 −0 base/bits.hpp
  5. +17 −0 base/bits_body.hpp
  6. +29 −0 base/bits_test.cpp
  7. +11 −16 numerics/polynomial_evaluators_body.hpp
3 changes: 3 additions & 0 deletions base/base.vcxproj
Original file line number Diff line number Diff line change
@@ -21,6 +21,8 @@
<ClInclude Include="base32768_body.hpp" />
<ClInclude Include="base64.hpp" />
<ClInclude Include="base64_body.hpp" />
<ClInclude Include="bits.hpp" />
<ClInclude Include="bits_body.hpp" />
<ClInclude Include="bundle.hpp" />
<ClInclude Include="constant_function.hpp" />
<ClInclude Include="disjoint_sets.hpp" />
@@ -78,6 +80,7 @@
<ClCompile Include="array_test.cpp" />
<ClCompile Include="base32768_test.cpp" />
<ClCompile Include="base64_test.cpp" />
<ClCompile Include="bits_test.cpp" />
<ClCompile Include="bundle.cpp" />
<ClCompile Include="bundle_test.cpp" />
<ClCompile Include="disjoint_sets_test.cpp" />
9 changes: 9 additions & 0 deletions base/base.vcxproj.filters
Original file line number Diff line number Diff line change
@@ -188,6 +188,12 @@
<ClInclude Include="zfp_compressor_body.hpp">
<Filter>Source Files</Filter>
</ClInclude>
<ClInclude Include="bits.hpp">
<Filter>Header Files</Filter>
</ClInclude>
<ClInclude Include="bits_body.hpp">
<Filter>Source Files</Filter>
</ClInclude>
</ItemGroup>
<ItemGroup>
<ClCompile Include="not_null_test.cpp">
@@ -247,5 +253,8 @@
<ClCompile Include="zfp_compressor.cpp">
<Filter>Source Files</Filter>
</ClCompile>
<ClCompile Include="bits_test.cpp">
<Filter>Test Files</Filter>
</ClCompile>
</ItemGroup>
</Project>
10 changes: 3 additions & 7 deletions base/base32768_body.hpp
Original file line number Diff line number Diff line change
@@ -13,6 +13,7 @@
#include <type_traits>
#include <vector>

#include "base/bits.hpp"
#include "base/macros.hpp"
#include "glog/logging.h"

@@ -24,11 +25,6 @@ namespace principia {
namespace base {
namespace internal_base32768 {

// Ceiling log2 of n. 8 -> 3, 7 -> 2.
constexpr int CeilingLog2(int const n) {
return n == 1 ? 0 : CeilingLog2(n >> 1) + 1;
}

// A repertoire is used to encode or decode integers into Basic Multilingual
// Plane code points.
class Repertoire {
@@ -64,7 +60,7 @@ class CachingRepertoire : public Repertoire {
// and must decode characters which lie within the blocks of this repertoire.
std::array<char16_t, block_count * block_size> encoding_cache_;
// Using a C array because MSVC gets confused with an std::array.
std::conditional_t<(CeilingLog2(block_size * block_count) > 8),
std::conditional_t<(FloorLog2(block_size * block_count) > 8),
std::uint16_t,
std::uint8_t>
decoding_cache_[std::numeric_limits<char16_t>::max()];
@@ -83,7 +79,7 @@ template<std::int64_t block_count_plus_1>
constexpr CachingRepertoire<block_size, block_count>::CachingRepertoire(
char16_t const (&blocks)[block_count_plus_1])
: blocks_(blocks),
encoding_bits_(CeilingLog2(block_size * block_count)),
encoding_bits_(FloorLog2(block_size * block_count)),
decoding_cache_() {
// Don't do pointer arithmetic in this constructor, it confuses MSVC.
static_assert(block_count_plus_1 == block_count + 1,
16 changes: 16 additions & 0 deletions base/bits.hpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,16 @@

#pragma once

namespace principia {
namespace base {

// Floor log2 of n, or 0 for n = 0. 8 ↦ 3, 7 ↦ 2.
constexpr int FloorLog2(int n);

// Greatest power of 2 less than or equal to n. 8 ↦ 8, 7 ↦ 4.
constexpr int PowerOf2Le(int n);

} // namespace base
} // namespace principia

#include "base/bits_body.hpp"
17 changes: 17 additions & 0 deletions base/bits_body.hpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,17 @@
#pragma once

#include "base/bits.hpp"

namespace principia {
namespace base {

constexpr int FloorLog2(int const n) {
return n == 0 ? 0 : n == 1 ? 0 : FloorLog2(n >> 1) + 1;
}

constexpr int PowerOf2Le(int const n) {
return n == 0 ? 0 : n == 1 ? 1 : PowerOf2Le(n >> 1) << 1;
}

} // namespace base
} // namespace principia
29 changes: 29 additions & 0 deletions base/bits_test.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,29 @@
#include "base/bits.hpp"

#include "gtest/gtest.h"

namespace principia {
namespace base {

TEST(BitsTest, FloorLog2) {
EXPECT_EQ(0, FloorLog2(0));
EXPECT_EQ(0, FloorLog2(1));
EXPECT_EQ(1, FloorLog2(2));
EXPECT_EQ(1, FloorLog2(3));
EXPECT_EQ(2, FloorLog2(4));
EXPECT_EQ(2, FloorLog2(7));
EXPECT_EQ(3, FloorLog2(8));
}

TEST(BitsTest, PowerOf2Le) {
EXPECT_EQ(0, PowerOf2Le(0));
EXPECT_EQ(1, PowerOf2Le(1));
EXPECT_EQ(2, PowerOf2Le(2));
EXPECT_EQ(2, PowerOf2Le(3));
EXPECT_EQ(4, PowerOf2Le(4));
EXPECT_EQ(4, PowerOf2Le(7));
EXPECT_EQ(8, PowerOf2Le(8));
}

} // namespace base
} // namespace principia
27 changes: 11 additions & 16 deletions numerics/polynomial_evaluators_body.hpp
Original file line number Diff line number Diff line change
@@ -5,19 +5,14 @@
#include <cstddef>
#include <tuple>

#include "base/bits.hpp"

namespace principia {
namespace numerics {
namespace internal_polynomial_evaluators {

// Greatest power of 2 less than or equal to n. 8 -> 8, 7 -> 4.
constexpr int FloorOfPowerOf2(int const n) {
return n == 0 ? 0 : n == 1 ? 1 : FloorOfPowerOf2(n >> 1) << 1;
}

// Ceiling log2 of n, or 0 for n = 0. 8 -> 3, 7 -> 2.
constexpr int CeilingLog2(int const n) {
return n == 0 ? 0 : n == 1 ? 0 : CeilingLog2(n >> 1) + 1;
}
using base::FloorLog2;
using base::PowerOf2Le;

// Generator for repeated squaring:
// SquareGenerator<Length, 0>::Type is Exponentiation<Length, 2>
@@ -69,7 +64,7 @@ auto SquaresGenerator<Argument, std::index_sequence<orders...>>::
template<typename Value, typename Argument, int degree, int low, int subdegree>
struct InternalEstrinEvaluator {
using ArgumentSquaresGenerator =
SquaresGenerator<Argument, std::make_index_sequence<CeilingLog2(degree)>>;
SquaresGenerator<Argument, std::make_index_sequence<FloorLog2(degree)>>;
using ArgumentSquares = typename ArgumentSquaresGenerator::Type;
using Coefficients =
typename PolynomialInMonomialBasis<Value, Argument, degree,
@@ -88,7 +83,7 @@ struct InternalEstrinEvaluator {
template<typename Value, typename Argument, int degree, int low>
struct InternalEstrinEvaluator<Value, Argument, degree, low, 1> {
using ArgumentSquaresGenerator =
SquaresGenerator<Argument, std::make_index_sequence<CeilingLog2(degree)>>;
SquaresGenerator<Argument, std::make_index_sequence<FloorLog2(degree)>>;
using ArgumentSquares = typename ArgumentSquaresGenerator::Type;
using Coefficients =
typename PolynomialInMonomialBasis<Value, Argument, degree,
@@ -107,7 +102,7 @@ struct InternalEstrinEvaluator<Value, Argument, degree, low, 1> {
template<typename Value, typename Argument, int degree, int low>
struct InternalEstrinEvaluator<Value, Argument, degree, low, 0> {
using ArgumentSquaresGenerator =
SquaresGenerator<Argument, std::make_index_sequence<CeilingLog2(degree)>>;
SquaresGenerator<Argument, std::make_index_sequence<FloorLog2(degree)>>;
using ArgumentSquares = typename ArgumentSquaresGenerator::Type;
using Coefficients =
typename PolynomialInMonomialBasis<Value, Argument, degree,
@@ -132,9 +127,9 @@ InternalEstrinEvaluator<Value, Argument, degree, low, subdegree>::Evaluate(
static_assert(subdegree >= 2,
"Unexpected subdegree in InternalEstrinEvaluator::Evaluate");
// |n| is used to select |argument^(2^(n + 1))| = |argument^m|.
constexpr int n = CeilingLog2(subdegree) - 1;
constexpr int n = FloorLog2(subdegree) - 1;
// |m| is |2^(n + 1)|.
constexpr int m = FloorOfPowerOf2(subdegree);
constexpr int m = PowerOf2Le(subdegree);
return InternalEstrinEvaluator<Value, Argument, degree,
low, m - 1>::
Evaluate(coefficients, argument, argument_squares) +
@@ -154,9 +149,9 @@ EvaluateDerivative(Coefficients const& coefficients,
"Unexpected subdegree in InternalEstrinEvaluator::"
"EvaluateDerivative");
// |n| is used to select |argument^(2^(n + 1))| = |argument^m|.
constexpr int n = CeilingLog2(subdegree) - 1;
constexpr int n = FloorLog2(subdegree) - 1;
// |m| is |2^(n + 1)|.
constexpr int m = FloorOfPowerOf2(subdegree);
constexpr int m = PowerOf2Le(subdegree);
return InternalEstrinEvaluator<Value, Argument, degree,
low, m - 1>::
EvaluateDerivative(coefficients, argument, argument_squares) +