src/mem/cache/compressors/cpack.hh

   1 /*
   2  * Copyright (c) 2018-2019 Inria
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Daniel Carvalho
  29  */
  30
  31 /** @file
  32  * Definition of CPack compression, from "C-Pack: A High-Performance
  33  * Microprocessor Cache Compression Algorithm".
  34  */
  35
  36 #ifndef __MEM_CACHE_COMPRESSORS_CPACK_HH__
  37 #define __MEM_CACHE_COMPRESSORS_CPACK_HH__
  38
  39 #include <cstdint>
  40 #include <map>
  41 #include <memory>
  42
  43 #include "base/types.hh"
  44 #include "mem/cache/compressors/dictionary_compressor.hh"
  45
  46 struct CPackParams;
  47
  48 class CPack : public DictionaryCompressor<uint32_t>
  49 {
  50   private:
  51     using DictionaryEntry = DictionaryCompressor<uint32_t>::DictionaryEntry;
  52
  53     // Forward declaration of all possible patterns
  54     class PatternZZZZ;
  55     class PatternXXXX;
  56     class PatternMMMM;
  57     class PatternMMXX;
  58     class PatternZZZX;
  59     class PatternMMMX;
  60
  61     /**
  62      * The patterns proposed in the paper. Each letter represents a byte:
  63      * Z is a null byte, M is a dictionary match, X is a new value.
  64      * These are used as indexes to reference the pattern data. If a new
  65      * pattern is added, it must be done before NUM_PATTERNS.
  66      */
  67     typedef enum {
  68         ZZZZ, XXXX, MMMM, MMXX, ZZZX, MMMX, NUM_PATTERNS
  69     } PatternNumber;
  70
  71     /**
  72      * Convenience factory declaration. The templates must be organized by
  73      * size, with the smallest first, and "no-match" last.
  74      */
  75     using PatternFactory = Factory<PatternZZZZ, PatternMMMM, PatternZZZX,
  76                                    PatternMMMX, PatternMMXX, PatternXXXX>;
  77
  78     uint64_t getNumPatterns() const override { return NUM_PATTERNS; }
  79
  80     std::string
  81     getName(int number) const override
  82     {
  83         static std::map<int, std::string> patternNames = {
  84             {ZZZZ, "ZZZZ"}, {XXXX, "XXXX"}, {MMMM, "MMMM"},
  85             {MMXX, "MMXX"}, {ZZZX, "ZZZX"}, {MMMX, "MMMX"}
  86         };
  87
  88         return patternNames[number];
  89     };
  90
  91     std::unique_ptr<Pattern> getPattern(
  92         const DictionaryEntry& bytes,
  93         const DictionaryEntry& dict_bytes,
  94         const int match_location) const override
  95     {
  96         return PatternFactory::getPattern(bytes, dict_bytes, match_location);
  97     }
  98
  99     void addToDictionary(DictionaryEntry data) override;
 100
 101     /**
 102      * Apply compression.
 103      *
 104      * @param data The cache line to be compressed.
 105      * @param comp_lat Compression latency in number of cycles.
 106      * @param decomp_lat Decompression latency in number of cycles.
 107      * @return Cache line after compression.
 108      */
 109     std::unique_ptr<BaseCacheCompressor::CompressionData> compress(
 110         const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override;
 111
 112   public:
 113     /** Convenience typedef. */
 114      typedef CPackParams Params;
 115
 116     /**
 117      * Default constructor.
 118      */
 119     CPack(const Params *p);
 120
 121     /**
 122      * Default destructor.
 123      */
 124     ~CPack() {};
 125 };
 126
 127 class CPack::PatternZZZZ : public DictionaryCompressor::Pattern
 128 {
 129   public:
 130     PatternZZZZ(const DictionaryEntry bytes, const int match_location)
 131         : Pattern(ZZZZ, 0x0, 2, 0, 0, false) {}
 132
 133     static bool isPattern(const DictionaryEntry& bytes,
 134         const DictionaryEntry& dict_bytes,
 135         const int match_location)
 136     {
 137         return (bytes[3] == 0) && (bytes[2] == 0) && (bytes[1] == 0) &&
 138                (bytes[0] == 0);
 139     }
 140
 141     DictionaryEntry
 142     decompress(const DictionaryEntry dict_bytes) const override
 143     {
 144         return {0, 0, 0, 0};
 145     }
 146 };
 147
 148 class CPack::PatternXXXX : public UncompressedPattern
 149 {
 150   public:
 151     PatternXXXX(const DictionaryEntry bytes, const int match_location)
 152         : UncompressedPattern(XXXX, 0x1, 2, match_location, bytes)
 153     {
 154     }
 155 };
 156
 157 class CPack::PatternMMMM : public MaskedPattern<0xFFFFFFFF>
 158 {
 159   public:
 160     PatternMMMM(const DictionaryEntry bytes, const int match_location)
 161         : MaskedPattern<0xFFFFFFFF>(MMMM, 0x2, 6, match_location, bytes, true)
 162     {
 163     }
 164 };
 165
 166 class CPack::PatternMMXX : public MaskedPattern<0xFFFF0000>
 167 {
 168   public:
 169     PatternMMXX(const DictionaryEntry bytes, const int match_location)
 170         : MaskedPattern<0xFFFF0000>(MMXX, 0xC, 8, match_location, bytes, true)
 171     {
 172     }
 173 };
 174
 175 class CPack::PatternZZZX : public DictionaryCompressor::Pattern
 176 {
 177   private:
 178     /**
 179      * A copy of the unmatched byte.
 180      */
 181     const uint8_t byte;
 182
 183   public:
 184     PatternZZZX(const DictionaryEntry bytes, const int match_location)
 185         : Pattern(ZZZX, 0xD, 4, 1, 0, false), byte(bytes[0]) {}
 186
 187     static bool isPattern(const DictionaryEntry& bytes,
 188         const DictionaryEntry& dict_bytes,
 189         const int match_location)
 190     {
 191         return (bytes[3] == 0) && (bytes[2] == 0) && (bytes[1] == 0) &&
 192                (bytes[0] != 0);
 193     }
 194
 195     DictionaryEntry
 196     decompress(const DictionaryEntry dict_bytes) const override
 197     {
 198         return {byte, 0, 0, 0};
 199     }
 200 };
 201
 202 class CPack::PatternMMMX : public MaskedPattern<0xFFFFFF00>
 203 {
 204   public:
 205     PatternMMMX(const DictionaryEntry bytes, const int match_location)
 206         : MaskedPattern<0xFFFFFF00>(MMMX, 0xE, 8, match_location, bytes, true)
 207     {
 208     }
 209 };
 210
 211 #endif //__MEM_CACHE_COMPRESSORS_CPACK_HH__