compat.h

Go to the documentation of this file.

// Copyright 2019-2023 CERN and copyright holders of ALICE O2.
// See https://alice-o2.web.cern.ch/copyright for details of the copyright holders.
// All rights not expressly granted are reserved.
//
// This software is distributed under the terms of the GNU General Public
// License v3 (GPL Version 3), copied verbatim in the file "COPYING".
//
// In applying this license CERN does not waive the privileges and immunities
// granted to it by virtue of its status as an Intergovernmental Organization
// or submit itself to any jurisdiction.
 
 
#ifndef RANS_COMPAT_H_
#define RANS_COMPAT_H_
 
#ifdef __CLING__
#error rANS should not be exposed to root
#endif
 
#include <numeric>
 
#include "rANS/internal/common/typetraits.h"
 
#include "rANS/internal/containers/DenseHistogram.h"
#include "rANS/internal/containers/RenormedHistogram.h"
#include "rANS/internal/containers/DenseSymbolTable.h"
#include "rANS/internal/containers/Symbol.h"
#include "rANS/internal/containers/LowRangeDecoderTable.h"
 
#include "rANS/internal/encode/Encoder.h"
#include "rANS/internal/encode/SingleStreamEncoderImpl.h"
 
#include "rANS/internal/decode/Decoder.h"
#include "rANS/internal/decode/DecoderImpl.h"
 
#include "rANS/factory.h"
 
namespace o2::rans::compat
{
 
namespace defaults
{
namespace internal
{
inline constexpr size_t RenormingLowerBound = 31;
} // namespace internal
 
struct CoderPreset {
  inline static constexpr size_t nStreams = 2;
  inline static constexpr size_t renormingLowerBound = internal::RenormingLowerBound;
};
 
} // namespace defaults
 
namespace compatImpl
{
inline constexpr uint32_t MinRenormThreshold = 10;
inline constexpr uint32_t MaxRenormThreshold = 20;
} // namespace compatImpl
 
inline size_t computeRenormingPrecision(size_t nUsedAlphabetSymbols)
{
  const uint32_t minBits = o2::rans::utils::log2UInt(nUsedAlphabetSymbols);
  const uint32_t estimate = minBits * 3u / 2u;
  const uint32_t maxThreshold = std::max(minBits, compatImpl::MaxRenormThreshold);
  const uint32_t minThreshold = std::max(estimate, compatImpl::MinRenormThreshold);
 
  return std::min(minThreshold, maxThreshold);
};
 
template <typename source_T>
RenormedDenseHistogram<source_T> renorm(DenseHistogram<source_T> histogram, size_t newPrecision = 0)
{
  using namespace o2::rans::internal;
 
  constexpr size_t IncompressibleSymbolFrequency = 1;
 
  if (histogram.empty()) {
    LOG(warning) << "rescaling empty histogram";
  }
 
  size_t nUsedAlphabetSymbols = countNUsedAlphabetSymbols(histogram);
 
  if (newPrecision == 0) {
    newPrecision = computeRenormingPrecision(nUsedAlphabetSymbols);
  }
 
  const size_t alphabetSize = histogram.size() + 1;              // +1 for incompressible symbol
  std::vector<uint64_t> cumulativeFrequencies(alphabetSize + 1); // +1 to store total cumulative frequencies
  cumulativeFrequencies[0] = 0;
  std::inclusive_scan(histogram.begin(), histogram.end(), ++cumulativeFrequencies.begin(), std::plus<>(), 0ull);
  cumulativeFrequencies.back() = histogram.getNumSamples() + IncompressibleSymbolFrequency;
 
  auto getFrequency = [&cumulativeFrequencies](count_t i) {
    assert(cumulativeFrequencies[i + 1] >= cumulativeFrequencies[i]);
    return cumulativeFrequencies[i + 1] - cumulativeFrequencies[i];
  };
 
  // we will memorize only those entries which can be used
  const auto sortIdx = [&]() {
    std::vector<size_t> indices;
    indices.reserve(nUsedAlphabetSymbols + 1);
 
    for (size_t i = 0; i < alphabetSize; ++i) {
      if (getFrequency(i) != 0) {
        indices.push_back(i);
      }
    }
 
    std::sort(indices.begin(), indices.end(), [&](count_t i, count_t j) { return getFrequency(i) < getFrequency(j); });
    return indices;
  }();
 
  // resample distribution based on cumulative frequencies
  const count_t newCumulatedFrequency = utils::pow2(newPrecision);
  size_t nSamples = histogram.getNumSamples() + IncompressibleSymbolFrequency;
  assert(newCumulatedFrequency >= nUsedAlphabetSymbols);
  size_t needsShift = 0;
  for (size_t i = 0; i < sortIdx.size(); i++) {
    if (static_cast<count_t>(getFrequency(sortIdx[i])) * (newCumulatedFrequency - needsShift) / nSamples >= 1) {
      break;
    }
    needsShift++;
  }
 
  size_t shift = 0;
  auto beforeUpdate = cumulativeFrequencies[0];
  for (size_t i = 0; i < alphabetSize; i++) {
    auto& nextCumulative = cumulativeFrequencies[i + 1];
    uint64_t oldFrequeny = nextCumulative - beforeUpdate;
    if (oldFrequeny && oldFrequeny * (newCumulatedFrequency - needsShift) / nSamples < 1) {
      shift++;
    }
    beforeUpdate = cumulativeFrequencies[i + 1];
    nextCumulative = (static_cast<uint64_t>(newCumulatedFrequency - needsShift) * nextCumulative) / nSamples + shift;
  }
  assert(shift == needsShift);
 
  // verify
#if !defined(NDEBUG)
  assert(cumulativeFrequencies.front() == 0);
  assert(cumulativeFrequencies.back() == newCumulatedFrequency);
  size_t i = 0;
  for (auto frequency : histogram) {
    if (frequency == 0) {
      assert(cumulativeFrequencies[i + 1] == cumulativeFrequencies[i]);
    } else {
      assert(cumulativeFrequencies[i + 1] > cumulativeFrequencies[i]);
    }
    ++i;
  }
#endif
 
  typename RenormedDenseHistogram<source_T>::container_type rescaledFrequencies(histogram.size(), histogram.getOffset());
 
  assert(cumulativeFrequencies.size() == histogram.size() + 2);
  // calculate updated frequencies
  for (size_t i = 0; i < histogram.size(); ++i) {
    rescaledFrequencies(i) = getFrequency(i);
  }
  const typename RenormedDenseHistogram<source_T>::value_type incompressibleSymbolFrequency = getFrequency(histogram.size());
 
  return RenormedDenseHistogram<source_T>{std::move(rescaledFrequencies), newPrecision, incompressibleSymbolFrequency};
};
 
class makeEncoder
{
 
 public:
  template <typename container_T>
  [[nodiscard]] inline static constexpr decltype(auto) fromRenormed(const RenormedHistogramConcept<container_T>& renormed)
  {
    using namespace o2::rans::internal;
    using source_type = typename RenormedHistogramConcept<container_T>::source_type;
    using symbol_type = internal::PrecomputedSymbol;
    using coder_command = SingleStreamEncoderImpl<mRenormingLowerBound>;
    using symbolTable_type = DenseSymbolTable<source_type, symbol_type>;
    using encoderType = Encoder<coder_command, symbolTable_type, mNstreams>;
 
    return encoderType{renormed};
  };
 
  template <typename source_T>
  [[nodiscard]] inline static decltype(auto) fromHistogram(DenseHistogram<source_T> histogram, size_t renormingPrecision = 0)
  {
    const auto renormedHistogram = o2::rans::compat::renorm(std::move(histogram), renormingPrecision);
    return makeEncoder::fromRenormed(renormedHistogram);
  };
 
  template <typename source_IT>
  [[nodiscard]] inline static decltype(auto) fromSamples(source_IT begin, source_IT end, size_t renormingPrecision = 0)
  {
    auto histogram = makeDenseHistogram::fromSamples(begin, end);
 
    return makeEncoder::fromHistogram(std::move(histogram), renormingPrecision);
  };
 
  template <typename source_T>
  [[nodiscard]] inline static decltype(auto) fromSamples(gsl::span<const source_T> range, size_t renormingPrecision = 0)
  {
    auto histogram = makeDenseHistogram::template fromSamples(range);
    return makeEncoder::fromHistogram(std::move(histogram), renormingPrecision);
  };
 
 private:
  static constexpr CoderTag mCoderTag = CoderTag::SingleStream;
  static constexpr size_t mNstreams = defaults::CoderPreset::nStreams;
  static constexpr size_t mRenormingLowerBound = defaults::CoderPreset::renormingLowerBound;
};
 
class makeDecoder
{
 
  using this_type = makeDecoder;
 
 public:
  template <typename container_T>
  [[nodiscard]] inline static constexpr decltype(auto) fromRenormed(const RenormedHistogramConcept<container_T>& renormed)
  {
    using namespace internal;
 
    using source_type = typename RenormedHistogramConcept<container_T>::source_type;
    using coder_type = DecoderImpl<mRenormingLowerBound>;
    using decoder_type = Decoder<source_type, coder_type>;
 
    return decoder_type{renormed};
  };
 
  template <typename source_T>
  [[nodiscard]] inline static decltype(auto) fromHistogram(DenseHistogram<source_T> histogram, size_t renormingPrecision = 0)
  {
    const auto renormedHistogram = o2::rans::compat::renorm(std::move(histogram), renormingPrecision);
    return this_type::fromRenormed(renormedHistogram);
  };
 
  template <typename source_IT>
  [[nodiscard]] inline static decltype(auto) fromSamples(source_IT begin, source_IT end, size_t renormingPrecision = 0)
  {
    auto histogram = makeDenseHistogram::fromSamples(begin, end);
    return this_type::fromHistogram(std::move(histogram), renormingPrecision);
  };
 
  template <typename source_T>
  [[nodiscard]] inline static decltype(auto) fromSamples(gsl::span<const source_T> range, size_t renormingPrecision = 0)
  {
    auto histogram = makeDenseHistogram::fromSamples(range);
    return this_type::fromHistogram(std::move(histogram), renormingPrecision);
  };
 
 private:
  static constexpr CoderTag mCoderTag = CoderTag::SingleStream;
  static constexpr size_t mNstreams = defaults::CoderPreset::nStreams;
  static constexpr size_t mRenormingLowerBound = defaults::CoderPreset::renormingLowerBound;
};
 
template <typename source_T>
inline size_t getAlphabetRangeBits(const DenseHistogram<source_T>& histogram) noexcept
{
  using namespace o2::rans::internal;
  const auto view = trim(makeHistogramView(histogram));
  return internal::numBitsForNSymbols(view.size());
};
 
template <typename source_T>
inline size_t getAlphabetRangeBits(const RenormedDenseHistogram<source_T>& histogram) noexcept
{
  using namespace o2::rans::internal;
  const auto view = trim(makeHistogramView(histogram));
  return internal::numBitsForNSymbols(view.size() + histogram.hasIncompressibleSymbol());
};
 
template <typename source_T, typename symbol_T>
inline size_t getAlphabetRangeBits(const DenseSymbolTable<source_T, symbol_T>& symbolTable) noexcept
{
  const bool hasIncompressibleSymbol = symbolTable.getEscapeSymbol().getFrequency() > 0;
  return internal::numBitsForNSymbols(symbolTable.size() + hasIncompressibleSymbol);
};
 
inline size_t calculateMaxBufferSizeB(size_t nElements, size_t rangeBits)
{
  constexpr size_t sizeofStreamT = sizeof(uint32_t);
  //  // RS: w/o safety margin the o2-test-ctf-io produces an overflow in the Encoder::process
  //  constexpr size_t SaferyMargin = 16;
  //  return std::ceil(1.20 * (num * rangeBits * 1.0) / (sizeofStreamT * 8.0)) + SaferyMargin;
  return nElements * sizeofStreamT;
}
 
template <typename source_T>
using encoder_type = decltype(makeEncoder::fromRenormed(RenormedDenseHistogram<source_T>{}));
 
template <typename source_T>
using decoder_type = decltype(makeDecoder::fromRenormed(RenormedDenseHistogram<source_T>{}));
 
} // namespace o2::rans::compat
 
#endif /* RANS_COMPAT_H_ */