dictionary_compressor.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2018-2020 Inria
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
#ifndef __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
#define __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
 
#include <array>
#include <cstdint>
#include <map>
#include <memory>
#include <string>
#include <type_traits>
#include <vector>
 
#include "base/bitfield.hh"
#include "base/statistics.hh"
#include "base/types.hh"
#include "mem/cache/compressors/base.hh"
 
struct BaseDictionaryCompressorParams;
 
namespace Compressor {
 
class BaseDictionaryCompressor : public Base
{
  protected:
    const std::size_t dictionarySize;
 
    std::size_t numEntries;
 
    struct DictionaryStats : public Stats::Group
    {
        const BaseDictionaryCompressor& compressor;
 
        DictionaryStats(BaseStats &base_group,
            BaseDictionaryCompressor& _compressor);
 
        void regStats() override;
 
        Stats::Vector patterns;
    } dictionaryStats;
 
    virtual uint64_t getNumPatterns() const = 0;
 
    virtual std::string getName(int number) const = 0;
 
  public:
    typedef BaseDictionaryCompressorParams Params;
    BaseDictionaryCompressor(const Params &p);
    ~BaseDictionaryCompressor() = default;
};
 
template <class T>
class DictionaryCompressor : public BaseDictionaryCompressor
{
  protected:
    typedef std::array<uint8_t, sizeof(T)> DictionaryEntry;
 
    class CompData;
 
    // Forward declaration of a pattern
    class Pattern;
    class UncompressedPattern;
    template <T mask>
    class MaskedPattern;
    template <T value, T mask>
    class MaskedValuePattern;
    template <T mask, int location>
    class LocatedMaskedPattern;
    template <class RepT>
    class RepeatedValuePattern;
    template <std::size_t DeltaSizeBits>
    class DeltaPattern;
    template <unsigned N>
    class SignExtendedPattern;
 
    template <class Head, class... Tail>
    struct Factory
    {
        static std::unique_ptr<Pattern> getPattern(
            const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
            const int match_location)
        {
            // If match this pattern, instantiate it. If a negative match
            // location is used, the patterns that use the dictionary bytes
            // must return false. This is used when there are no dictionary
            // entries yet
            if (Head::isPattern(bytes, dict_bytes, match_location)) {
                return std::unique_ptr<Pattern>(
                            new Head(bytes, match_location));
            // Otherwise, go for next pattern
            } else {
                return Factory<Tail...>::getPattern(bytes, dict_bytes,
                                                    match_location);
            }
        }
    };
 
    template <class Head>
    struct Factory<Head>
    {
        static_assert(std::is_base_of<UncompressedPattern, Head>::value,
            "The last pattern must always be derived from the uncompressed "
            "pattern.");
 
        static std::unique_ptr<Pattern>
        getPattern(const DictionaryEntry& bytes,
            const DictionaryEntry& dict_bytes, const int match_location)
        {
            return std::unique_ptr<Pattern>(new Head(bytes, match_location));
        }
    };
 
    std::vector<DictionaryEntry> dictionary;
 
    virtual std::unique_ptr<Pattern>
    getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
        const int match_location) const = 0;
 
    std::unique_ptr<Pattern> compressValue(const T data);
 
    T decompressValue(const Pattern* pattern);
 
    virtual void resetDictionary();
 
    virtual void addToDictionary(const DictionaryEntry data) = 0;
 
    virtual std::unique_ptr<DictionaryCompressor::CompData>
    instantiateDictionaryCompData() const;
 
    std::unique_ptr<Base::CompressionData> compress(
        const std::vector<Chunk>& chunks);
 
    std::unique_ptr<Base::CompressionData> compress(
        const std::vector<Chunk>& chunks,
        Cycles& comp_lat, Cycles& decomp_lat) override;
 
    using BaseDictionaryCompressor::compress;
 
    void decompress(const CompressionData* comp_data, uint64_t* data) override;
 
    static DictionaryEntry toDictionaryEntry(T value);
 
    static T fromDictionaryEntry(const DictionaryEntry& entry);
 
  public:
    typedef BaseDictionaryCompressorParams Params;
    DictionaryCompressor(const Params &p);
    ~DictionaryCompressor() = default;
};
 
template <class T>
class DictionaryCompressor<T>::Pattern
{
  protected:
    const int patternNumber;
 
    const uint8_t code;
 
    const uint8_t length;
 
    const uint8_t numUnmatchedBits;
 
    const int matchLocation;
 
    const bool allocate;
 
  public:
    Pattern(const int number, const uint64_t code,
            const uint64_t metadata_length, const uint64_t num_unmatched_bits,
            const int match_location, const bool allocate = true)
        : patternNumber(number), code(code), length(metadata_length),
          numUnmatchedBits(num_unmatched_bits),
          matchLocation(match_location), allocate(allocate)
    {
    }
 
    virtual ~Pattern() = default;
 
    int getPatternNumber() const { return patternNumber; };
 
    uint8_t getCode() const { return code; }
 
    uint8_t getMatchLocation() const { return matchLocation; }
 
    virtual std::size_t
    getSizeBits() const
    {
        return numUnmatchedBits + length;
    }
 
    bool shouldAllocate() const { return allocate; }
 
    std::string
    print() const
    {
        return csprintf("pattern %s (encoding %x, size %u bits)",
                        getPatternNumber(), getCode(), getSizeBits());
    }
 
    virtual DictionaryEntry decompress(
        const DictionaryEntry dict_bytes) const = 0;
};
 
template <class T>
class DictionaryCompressor<T>::CompData : public CompressionData
{
  public:
    std::vector<std::unique_ptr<Pattern>> entries;
 
    CompData();
    ~CompData() = default;
 
    virtual void addEntry(std::unique_ptr<Pattern>);
};
 
template <class T>
class DictionaryCompressor<T>::UncompressedPattern
    : public DictionaryCompressor<T>::Pattern
{
  private:
    const DictionaryEntry data;
 
  public:
    UncompressedPattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const int match_location,
        const DictionaryEntry bytes)
      : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
            sizeof(T) * 8, match_location, true),
        data(bytes)
    {
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
        const int match_location)
    {
        // An entry can always be uncompressed
        return true;
    }
 
    DictionaryEntry
    decompress(const DictionaryEntry dict_bytes) const override
    {
        return data;
    }
};
 
template <class T>
template <T mask>
class DictionaryCompressor<T>::MaskedPattern
    : public DictionaryCompressor<T>::Pattern
{
  private:
    static_assert(mask != 0, "The pattern's value mask must not be zero. Use "
        "the uncompressed pattern instead.");
 
    const T bits;
 
  public:
    MaskedPattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const int match_location,
        const DictionaryEntry bytes,
        const bool allocate = true)
      : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
            popCount(static_cast<T>(~mask)), match_location, allocate),
        bits(DictionaryCompressor<T>::fromDictionaryEntry(bytes) & ~mask)
    {
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
        const int match_location)
    {
        const T masked_bytes =
            DictionaryCompressor<T>::fromDictionaryEntry(bytes) & mask;
        const T masked_dict_bytes =
            DictionaryCompressor<T>::fromDictionaryEntry(dict_bytes) & mask;
        return (match_location >= 0) && (masked_bytes == masked_dict_bytes);
    }
 
    DictionaryEntry
    decompress(const DictionaryEntry dict_bytes) const override
    {
        const T masked_dict_bytes =
            DictionaryCompressor<T>::fromDictionaryEntry(dict_bytes) & mask;
        return DictionaryCompressor<T>::toDictionaryEntry(
            bits | masked_dict_bytes);
    }
};
 
template <class T>
template <T value, T mask>
class DictionaryCompressor<T>::MaskedValuePattern
    : public MaskedPattern<mask>
{
  private:
    static_assert(mask != 0, "The pattern's value mask must not be zero.");
 
  public:
    MaskedValuePattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const int match_location,
        const DictionaryEntry bytes,
        const bool allocate = false)
      : MaskedPattern<mask>(number, code, metadata_length, match_location,
            bytes, allocate)
    {
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
        const int match_location)
    {
        // Compare the masked fixed value to the value being checked for
        // patterns. Since the dictionary is not being used the match_location
        // is irrelevant.
        const T masked_bytes =
            DictionaryCompressor<T>::fromDictionaryEntry(bytes) & mask;
        return ((value & mask) == masked_bytes);
    }
 
    DictionaryEntry
    decompress(const DictionaryEntry dict_bytes) const override
    {
        return MaskedPattern<mask>::decompress(
            DictionaryCompressor<T>::toDictionaryEntry(value));
    }
};
 
template <class T>
template <T mask, int location>
class DictionaryCompressor<T>::LocatedMaskedPattern
    : public MaskedPattern<mask>
{
  public:
    LocatedMaskedPattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const int match_location,
        const DictionaryEntry bytes,
        const bool allocate = true)
      : MaskedPattern<mask>(number, code, metadata_length, match_location,
            bytes, allocate)
    {
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
        const int match_location)
    {
        // Besides doing the regular masked pattern matching, the match
        // location must match perfectly with this instance's
        return (match_location == location) &&
            MaskedPattern<mask>::isPattern(bytes, dict_bytes, match_location);
    }
};
 
template <class T>
template <class RepT>
class DictionaryCompressor<T>::RepeatedValuePattern
    : public DictionaryCompressor<T>::Pattern
{
  private:
    static_assert(sizeof(T) > sizeof(RepT), "The repeated value's type must "
        "be smaller than the dictionary entry's type.");
 
    RepT value;
 
  public:
    RepeatedValuePattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const int match_location,
        const DictionaryEntry bytes,
        const bool allocate = true)
      : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
            8 * sizeof(RepT), match_location, allocate),
        value(DictionaryCompressor<T>::fromDictionaryEntry(bytes))
    {
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
        const int match_location)
    {
        // Parse the dictionary entry in a RepT granularity, and if all values
        // are equal, this is a repeated value pattern. Since the dictionary
        // is not being used, the match_location is irrelevant
        T bytes_value = DictionaryCompressor<T>::fromDictionaryEntry(bytes);
        const RepT rep_value = bytes_value;
        for (int i = 0; i < (sizeof(T) / sizeof(RepT)); i++) {
            RepT cur_value = bytes_value;
            if (cur_value != rep_value) {
                return false;
            }
            bytes_value >>= 8 * sizeof(RepT);
        }
        return true;
    }
 
    DictionaryEntry
    decompress(const DictionaryEntry dict_bytes) const override
    {
        // The decompressed value is just multiple consecutive instances of
        // the same value
        T decomp_value = 0;
        for (int i = 0; i < (sizeof(T) / sizeof(RepT)); i++) {
            decomp_value <<= 8 * sizeof(RepT);
            decomp_value |= value;
        }
        return DictionaryCompressor<T>::toDictionaryEntry(decomp_value);
    }
};
 
template <class T>
template <std::size_t DeltaSizeBits>
class DictionaryCompressor<T>::DeltaPattern
    : public DictionaryCompressor<T>::Pattern
{
  private:
    static_assert(DeltaSizeBits < (sizeof(T) * 8),
        "Delta size must be smaller than base size");
 
    const DictionaryEntry bytes;
 
  public:
    DeltaPattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const int match_location,
        const DictionaryEntry bytes)
      : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
            DeltaSizeBits, match_location, false),
        bytes(bytes)
    {
    }
 
    static bool
    isValidDelta(const DictionaryEntry& bytes,
        const DictionaryEntry& base_bytes)
    {
        const typename std::make_signed<T>::type limit = DeltaSizeBits ?
            mask(DeltaSizeBits - 1) : 0;
        const T value =
            DictionaryCompressor<T>::fromDictionaryEntry(bytes);
        const T base =
            DictionaryCompressor<T>::fromDictionaryEntry(base_bytes);
        const typename std::make_signed<T>::type delta = value - base;
        return (delta >= -limit) && (delta <= limit);
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes,
        const DictionaryEntry& dict_bytes, const int match_location)
    {
        return (match_location >= 0) && isValidDelta(bytes, dict_bytes);
    }
 
    DictionaryEntry
    decompress(const DictionaryEntry dict_bytes) const override
    {
        return bytes;
    }
};
 
template <class T>
template <unsigned N>
class DictionaryCompressor<T>::SignExtendedPattern
    : public DictionaryCompressor<T>::Pattern
{
  private:
    static_assert((N > 0) & (N <= (sizeof(T) * 8)),
        "The original data's type size must be smaller than the dictionary's");
 
    const T bits : N;
 
  public:
    SignExtendedPattern(const int number,
        const uint64_t code,
        const uint64_t metadata_length,
        const DictionaryEntry bytes,
        const bool allocate = false)
      : DictionaryCompressor<T>::Pattern(number, code, metadata_length, N,
            -1, allocate),
        bits(fromDictionaryEntry(bytes) & mask(N))
    {
    }
 
    static bool
    isPattern(const DictionaryEntry& bytes,
        const DictionaryEntry& dict_bytes, const int match_location)
    {
        const T data = DictionaryCompressor<T>::fromDictionaryEntry(bytes);
        return data == sext<N>(data & mask(N));
    }
 
    DictionaryEntry
    decompress(const DictionaryEntry dict_bytes) const override
    {
        return toDictionaryEntry(sext<N>(bits));
    }
};
 
} // namespace Compressor
 
#endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__