114089Sodanrc@yahoo.com.br/*
214089Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria
314089Sodanrc@yahoo.com.br * All rights reserved.
414089Sodanrc@yahoo.com.br *
514089Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without
614089Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are
714089Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright
814089Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer;
914089Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright
1014089Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the
1114089Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution;
1214089Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its
1314089Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from
1414089Sodanrc@yahoo.com.br * this software without specific prior written permission.
1514089Sodanrc@yahoo.com.br *
1614089Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1714089Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1814089Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1914089Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2014089Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2114089Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2214089Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2314089Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2414089Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2514089Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2614089Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2714089Sodanrc@yahoo.com.br *
2814089Sodanrc@yahoo.com.br * Authors: Daniel Carvalho
2914089Sodanrc@yahoo.com.br */
3014089Sodanrc@yahoo.com.br
3114089Sodanrc@yahoo.com.br/** @file
3214089Sodanrc@yahoo.com.br * Definition of CPack compression, from "C-Pack: A High-Performance
3314089Sodanrc@yahoo.com.br * Microprocessor Cache Compression Algorithm".
3414089Sodanrc@yahoo.com.br *
3514089Sodanrc@yahoo.com.br * The dictionary is composed of 32-bit entries.
3614089Sodanrc@yahoo.com.br *
3714089Sodanrc@yahoo.com.br * The patterns are implemented as individual classes that have a checking
3814089Sodanrc@yahoo.com.br * function isPattern(), to determine if the data fits the pattern, and a
3914089Sodanrc@yahoo.com.br * decompress() function, which decompresses the contents of a pattern.
4014089Sodanrc@yahoo.com.br * Every new pattern must inherit from the Pattern class and be added to the
4114089Sodanrc@yahoo.com.br * patternFactory.
4214089Sodanrc@yahoo.com.br */
4314089Sodanrc@yahoo.com.br
4414089Sodanrc@yahoo.com.br#ifndef __MEM_CACHE_COMPRESSORS_CPACK_HH__
4514089Sodanrc@yahoo.com.br#define __MEM_CACHE_COMPRESSORS_CPACK_HH__
4614089Sodanrc@yahoo.com.br
4714089Sodanrc@yahoo.com.br#include <array>
4814089Sodanrc@yahoo.com.br#include <cstdint>
4914089Sodanrc@yahoo.com.br#include <map>
5014089Sodanrc@yahoo.com.br#include <memory>
5114089Sodanrc@yahoo.com.br#include <vector>
5214089Sodanrc@yahoo.com.br
5314089Sodanrc@yahoo.com.br#include "base/types.hh"
5414089Sodanrc@yahoo.com.br#include "mem/cache/compressors/base.hh"
5514089Sodanrc@yahoo.com.br
5614089Sodanrc@yahoo.com.brstruct CPackParams;
5714089Sodanrc@yahoo.com.br
5814089Sodanrc@yahoo.com.brclass CPack : public BaseCacheCompressor
5914089Sodanrc@yahoo.com.br{
6014089Sodanrc@yahoo.com.br  private:
6114089Sodanrc@yahoo.com.br    /**
6214089Sodanrc@yahoo.com.br     * Compression data for CPack. It consists of a vector of patterns.
6314089Sodanrc@yahoo.com.br     */
6414089Sodanrc@yahoo.com.br    class CompData;
6514089Sodanrc@yahoo.com.br
6614089Sodanrc@yahoo.com.br    // Forward declaration of all possible patterns
6714089Sodanrc@yahoo.com.br    class Pattern;
6814089Sodanrc@yahoo.com.br    class PatternZZZZ;
6914089Sodanrc@yahoo.com.br    class PatternXXXX;
7014089Sodanrc@yahoo.com.br    class PatternMMMM;
7114089Sodanrc@yahoo.com.br    class PatternMMXX;
7214089Sodanrc@yahoo.com.br    class PatternZZZX;
7314089Sodanrc@yahoo.com.br    class PatternMMMX;
7414089Sodanrc@yahoo.com.br
7514089Sodanrc@yahoo.com.br    /**
7614089Sodanrc@yahoo.com.br     * Create a factory to determine if input matches a pattern. The if else
7714089Sodanrc@yahoo.com.br     * chains are constructed by recursion. The patterns should be explored
7814089Sodanrc@yahoo.com.br     * sorted by size for correct behaviour.
7914089Sodanrc@yahoo.com.br     */
8014089Sodanrc@yahoo.com.br    template <class Head, class... Tail>
8114089Sodanrc@yahoo.com.br    struct Factory
8214089Sodanrc@yahoo.com.br    {
8314089Sodanrc@yahoo.com.br        static std::unique_ptr<Pattern> getPattern(
8414089Sodanrc@yahoo.com.br            const std::array<uint8_t, 4>& bytes,
8514089Sodanrc@yahoo.com.br            const std::array<uint8_t, 4>& dict_bytes, const int match_location)
8614089Sodanrc@yahoo.com.br        {
8714089Sodanrc@yahoo.com.br            // If match this pattern, instantiate it. If a negative match
8814089Sodanrc@yahoo.com.br            // location is used, the patterns that use the dictionary bytes
8914089Sodanrc@yahoo.com.br            // must return false. This is used when there are no dictionary
9014089Sodanrc@yahoo.com.br            // entries yet
9114089Sodanrc@yahoo.com.br            if (Head::isPattern(bytes, dict_bytes, match_location)) {
9214089Sodanrc@yahoo.com.br                return std::unique_ptr<Pattern>(
9314089Sodanrc@yahoo.com.br                            new Head(bytes, match_location));
9414089Sodanrc@yahoo.com.br            // Otherwise, go for next pattern
9514089Sodanrc@yahoo.com.br            } else {
9614089Sodanrc@yahoo.com.br                return Factory<Tail...>::getPattern(bytes, dict_bytes,
9714089Sodanrc@yahoo.com.br                                                    match_location);
9814089Sodanrc@yahoo.com.br            }
9914089Sodanrc@yahoo.com.br        }
10014089Sodanrc@yahoo.com.br    };
10114089Sodanrc@yahoo.com.br
10214089Sodanrc@yahoo.com.br    /**
10314089Sodanrc@yahoo.com.br     * Specialization to end the recursion.
10414089Sodanrc@yahoo.com.br     */
10514089Sodanrc@yahoo.com.br    template <class Head>
10614089Sodanrc@yahoo.com.br    struct Factory<Head>
10714089Sodanrc@yahoo.com.br    {
10814089Sodanrc@yahoo.com.br        static std::unique_ptr<Pattern> getPattern(
10914089Sodanrc@yahoo.com.br            const std::array<uint8_t, 4>& bytes,
11014089Sodanrc@yahoo.com.br            const std::array<uint8_t, 4>& dict_bytes, const int match_location)
11114089Sodanrc@yahoo.com.br        {
11214089Sodanrc@yahoo.com.br            // Instantiate last pattern. Should be the XXXX pattern.
11314089Sodanrc@yahoo.com.br            return std::unique_ptr<Pattern>(new Head(bytes, match_location));
11414089Sodanrc@yahoo.com.br        }
11514089Sodanrc@yahoo.com.br    };
11614089Sodanrc@yahoo.com.br
11714089Sodanrc@yahoo.com.br    /**
11814089Sodanrc@yahoo.com.br     * Convenience factory declaration. The templates must be organized by
11914089Sodanrc@yahoo.com.br     * size, with the smallest first, and "no-match" last.
12014089Sodanrc@yahoo.com.br     */
12114089Sodanrc@yahoo.com.br    using PatternFactory = Factory<PatternZZZZ, PatternMMMM, PatternZZZX,
12214089Sodanrc@yahoo.com.br                                   PatternMMMX, PatternMMXX, PatternXXXX>;
12314089Sodanrc@yahoo.com.br
12414089Sodanrc@yahoo.com.br    /**
12514089Sodanrc@yahoo.com.br     * The dictionary.
12614089Sodanrc@yahoo.com.br     */
12714089Sodanrc@yahoo.com.br    std::vector<std::array<uint8_t, 4>> dictionary;
12814089Sodanrc@yahoo.com.br
12914089Sodanrc@yahoo.com.br    /**
13014089Sodanrc@yahoo.com.br     * Dictionary size.
13114089Sodanrc@yahoo.com.br     */
13214089Sodanrc@yahoo.com.br    const std::size_t dictionarySize;
13314089Sodanrc@yahoo.com.br
13414089Sodanrc@yahoo.com.br    /**
13514089Sodanrc@yahoo.com.br     * Number of valid entries in the dictionary.
13614089Sodanrc@yahoo.com.br     */
13714089Sodanrc@yahoo.com.br    std::size_t numEntries;
13814089Sodanrc@yahoo.com.br
13914089Sodanrc@yahoo.com.br    /**
14014089Sodanrc@yahoo.com.br     * @defgroup CompressionStats Compression specific statistics.
14114089Sodanrc@yahoo.com.br     * @{
14214089Sodanrc@yahoo.com.br     */
14314089Sodanrc@yahoo.com.br
14414089Sodanrc@yahoo.com.br    /**
14514089Sodanrc@yahoo.com.br     * Number of data entries that were compressed to each pattern.
14614089Sodanrc@yahoo.com.br     */
14714089Sodanrc@yahoo.com.br    Stats::Vector patternStats;
14814089Sodanrc@yahoo.com.br
14914089Sodanrc@yahoo.com.br    /**
15014089Sodanrc@yahoo.com.br     * @}
15114089Sodanrc@yahoo.com.br     */
15214089Sodanrc@yahoo.com.br
15314089Sodanrc@yahoo.com.br    /**
15414089Sodanrc@yahoo.com.br     * Compress data.
15514089Sodanrc@yahoo.com.br     *
15614089Sodanrc@yahoo.com.br     * @param data Data to be compressed.
15714089Sodanrc@yahoo.com.br     * @return The pattern this data matches.
15814089Sodanrc@yahoo.com.br     */
15914089Sodanrc@yahoo.com.br    std::unique_ptr<Pattern> compressWord(const uint32_t data);
16014089Sodanrc@yahoo.com.br
16114089Sodanrc@yahoo.com.br    /**
16214089Sodanrc@yahoo.com.br     * Decompress a word.
16314089Sodanrc@yahoo.com.br     *
16414089Sodanrc@yahoo.com.br     * @param pattern The pattern to be decompressed.
16514089Sodanrc@yahoo.com.br     * @return The decompressed word.
16614089Sodanrc@yahoo.com.br     */
16714089Sodanrc@yahoo.com.br    uint32_t decompressWord(const Pattern* pattern);
16814089Sodanrc@yahoo.com.br
16914089Sodanrc@yahoo.com.br    /**
17014089Sodanrc@yahoo.com.br     * Clear all dictionary entries.
17114089Sodanrc@yahoo.com.br     */
17214089Sodanrc@yahoo.com.br    void resetDictionary();
17314089Sodanrc@yahoo.com.br
17414089Sodanrc@yahoo.com.br    /**
17514089Sodanrc@yahoo.com.br     * Apply compression.
17614089Sodanrc@yahoo.com.br     *
17714089Sodanrc@yahoo.com.br     * @param data The cache line to be compressed.
17814089Sodanrc@yahoo.com.br     * @param comp_lat Compression latency in number of cycles.
17914089Sodanrc@yahoo.com.br     * @param decomp_lat Decompression latency in number of cycles.
18014089Sodanrc@yahoo.com.br     * @return Cache line after compression.
18114089Sodanrc@yahoo.com.br     */
18214089Sodanrc@yahoo.com.br    std::unique_ptr<BaseCacheCompressor::CompressionData> compress(
18314089Sodanrc@yahoo.com.br        const uint64_t* data, Cycles& comp_lat, Cycles& decomp_lat) override;
18414089Sodanrc@yahoo.com.br
18514089Sodanrc@yahoo.com.br    /**
18614089Sodanrc@yahoo.com.br     * Decompress data.
18714089Sodanrc@yahoo.com.br     *
18814089Sodanrc@yahoo.com.br     * @param comp_data Compressed cache line.
18914089Sodanrc@yahoo.com.br     * @param data The cache line to be decompressed.
19014089Sodanrc@yahoo.com.br     */
19114089Sodanrc@yahoo.com.br    void decompress(const CompressionData* comp_data, uint64_t* data) override;
19214089Sodanrc@yahoo.com.br
19314089Sodanrc@yahoo.com.br  public:
19414089Sodanrc@yahoo.com.br    /** Convenience typedef. */
19514089Sodanrc@yahoo.com.br     typedef CPackParams Params;
19614089Sodanrc@yahoo.com.br
19714089Sodanrc@yahoo.com.br    /**
19814089Sodanrc@yahoo.com.br     * Default constructor.
19914089Sodanrc@yahoo.com.br     */
20014089Sodanrc@yahoo.com.br    CPack(const Params *p);
20114089Sodanrc@yahoo.com.br
20214089Sodanrc@yahoo.com.br    /**
20314089Sodanrc@yahoo.com.br     * Default destructor.
20414089Sodanrc@yahoo.com.br     */
20514089Sodanrc@yahoo.com.br    ~CPack() {};
20614089Sodanrc@yahoo.com.br
20714089Sodanrc@yahoo.com.br    /**
20814089Sodanrc@yahoo.com.br     * Register local statistics.
20914089Sodanrc@yahoo.com.br     */
21014089Sodanrc@yahoo.com.br    void regStats() override;
21114089Sodanrc@yahoo.com.br};
21214089Sodanrc@yahoo.com.br
21314089Sodanrc@yahoo.com.br/**
21414089Sodanrc@yahoo.com.br * The compressed data is composed of multiple pattern entries. To add a new
21514089Sodanrc@yahoo.com.br * pattern one should inherit from this class and implement isPattern() and
21614089Sodanrc@yahoo.com.br * decompress. Then the new pattern must be added to the PatternFactory
21714089Sodanrc@yahoo.com.br * declaration in crescent order of size (in the CPack class). The pattern
21814089Sodanrc@yahoo.com.br * must be also added to the Name enum in the CPack::Pattern class before
21914089Sodanrc@yahoo.com.br * NUM_PATTERNS.
22014089Sodanrc@yahoo.com.br */
22114089Sodanrc@yahoo.com.brclass CPack::Pattern
22214089Sodanrc@yahoo.com.br{
22314089Sodanrc@yahoo.com.br  protected:
22414089Sodanrc@yahoo.com.br
22514089Sodanrc@yahoo.com.br    /**
22614089Sodanrc@yahoo.com.br     * The patterns proposed in the paper. Each letter represents a byte:
22714089Sodanrc@yahoo.com.br     * Z is a null byte, M is a dictionary match, X is a new value.
22814089Sodanrc@yahoo.com.br     * These are used as indexes to reference the pattern data. If a new
22914089Sodanrc@yahoo.com.br     * pattern is added, it must be done before NUM_PATTERNS.
23014089Sodanrc@yahoo.com.br     */
23114089Sodanrc@yahoo.com.br    typedef enum {
23214089Sodanrc@yahoo.com.br        ZZZZ, XXXX, MMMM, MMXX, ZZZX, MMMX, NUM_PATTERNS
23314089Sodanrc@yahoo.com.br    } PatternNumber;
23414089Sodanrc@yahoo.com.br
23514089Sodanrc@yahoo.com.br    /**
23614089Sodanrc@yahoo.com.br     * Pattern enum number.
23714089Sodanrc@yahoo.com.br     */
23814089Sodanrc@yahoo.com.br    const PatternNumber patternNumber;
23914089Sodanrc@yahoo.com.br
24014089Sodanrc@yahoo.com.br    /**
24114089Sodanrc@yahoo.com.br     * Code associated to the pattern.
24214089Sodanrc@yahoo.com.br     */
24314089Sodanrc@yahoo.com.br    const uint8_t code;
24414089Sodanrc@yahoo.com.br
24514089Sodanrc@yahoo.com.br    /**
24614089Sodanrc@yahoo.com.br     * Length, in bits, of the code and match location.
24714089Sodanrc@yahoo.com.br     */
24814089Sodanrc@yahoo.com.br    const uint8_t length;
24914089Sodanrc@yahoo.com.br
25014089Sodanrc@yahoo.com.br    /**
25114089Sodanrc@yahoo.com.br     * Number of unmatched bytes;
25214089Sodanrc@yahoo.com.br     */
25314089Sodanrc@yahoo.com.br    const uint8_t numUnmatchedBytes;
25414089Sodanrc@yahoo.com.br
25514089Sodanrc@yahoo.com.br    /**
25614089Sodanrc@yahoo.com.br     * Index representing the the match location.
25714089Sodanrc@yahoo.com.br     */
25814089Sodanrc@yahoo.com.br    const int matchLocation;
25914089Sodanrc@yahoo.com.br
26014089Sodanrc@yahoo.com.br    /**
26114089Sodanrc@yahoo.com.br     * Wether the pattern allocates a dictionary entry or not.
26214089Sodanrc@yahoo.com.br     */
26314089Sodanrc@yahoo.com.br    const bool allocate;
26414089Sodanrc@yahoo.com.br
26514089Sodanrc@yahoo.com.br    /**
26614089Sodanrc@yahoo.com.br     * Get code of this pattern.
26714089Sodanrc@yahoo.com.br     *
26814089Sodanrc@yahoo.com.br     * @return The code.
26914089Sodanrc@yahoo.com.br     */
27014089Sodanrc@yahoo.com.br    uint8_t getCode() const { return code; }
27114089Sodanrc@yahoo.com.br
27214089Sodanrc@yahoo.com.br  public:
27314089Sodanrc@yahoo.com.br    /**
27414089Sodanrc@yahoo.com.br     * Default constructor.
27514089Sodanrc@yahoo.com.br     *
27614089Sodanrc@yahoo.com.br     * @param number Pattern number.
27714089Sodanrc@yahoo.com.br     * @param code Code associated to this pattern.
27814089Sodanrc@yahoo.com.br     * @param metadata_length Length, in bits, of the code and match location.
27914089Sodanrc@yahoo.com.br     * @param num_unmatched_bytes Number of unmatched bytes.
28014089Sodanrc@yahoo.com.br     * @param match_location Index of the match location.
28114089Sodanrc@yahoo.com.br     */
28214089Sodanrc@yahoo.com.br    Pattern(const PatternNumber number, const uint64_t code,
28314089Sodanrc@yahoo.com.br            const uint64_t metadata_length, const uint64_t num_unmatched_bytes,
28414089Sodanrc@yahoo.com.br            const int match_location, const bool allocate = true)
28514089Sodanrc@yahoo.com.br        : patternNumber(number), code(code), length(metadata_length),
28614089Sodanrc@yahoo.com.br          numUnmatchedBytes(num_unmatched_bytes),
28714089Sodanrc@yahoo.com.br          matchLocation(match_location), allocate(allocate) {};
28814089Sodanrc@yahoo.com.br
28914089Sodanrc@yahoo.com.br    /**
29014089Sodanrc@yahoo.com.br     * Default destructor.
29114089Sodanrc@yahoo.com.br     */
29214089Sodanrc@yahoo.com.br    virtual ~Pattern() = default;
29314089Sodanrc@yahoo.com.br
29414089Sodanrc@yahoo.com.br    /**
29514089Sodanrc@yahoo.com.br     * Trick function to get the number of patterns.
29614089Sodanrc@yahoo.com.br     *
29714089Sodanrc@yahoo.com.br     * @return The number of defined patterns.
29814089Sodanrc@yahoo.com.br     */
29914089Sodanrc@yahoo.com.br    static uint64_t getNumPatterns() { return NUM_PATTERNS; };
30014089Sodanrc@yahoo.com.br
30114089Sodanrc@yahoo.com.br    /**
30214089Sodanrc@yahoo.com.br     * Get enum number associated to this pattern.
30314089Sodanrc@yahoo.com.br     *
30414089Sodanrc@yahoo.com.br     * @return The pattern enum number.
30514089Sodanrc@yahoo.com.br     */
30614089Sodanrc@yahoo.com.br    PatternNumber getPatternNumber() const { return patternNumber; };
30714089Sodanrc@yahoo.com.br
30814089Sodanrc@yahoo.com.br    /**
30914089Sodanrc@yahoo.com.br     * Get meta-name assigned to the given pattern.
31014089Sodanrc@yahoo.com.br     *
31114089Sodanrc@yahoo.com.br     * @param number The number of the pattern.
31214089Sodanrc@yahoo.com.br     * @return The meta-name of the pattern.
31314089Sodanrc@yahoo.com.br     */
31414089Sodanrc@yahoo.com.br    static std::string getName(int number)
31514089Sodanrc@yahoo.com.br    {
31614089Sodanrc@yahoo.com.br        static std::map<PatternNumber, std::string> patternNames = {
31714089Sodanrc@yahoo.com.br            {ZZZZ, "ZZZZ"}, {XXXX, "XXXX"}, {MMMM, "MMMM"},
31814089Sodanrc@yahoo.com.br            {MMXX, "MMXX"}, {ZZZX, "ZZZX"}, {MMMX, "MMMX"}
31914089Sodanrc@yahoo.com.br        };
32014089Sodanrc@yahoo.com.br
32114089Sodanrc@yahoo.com.br        return patternNames[(PatternNumber)number];
32214089Sodanrc@yahoo.com.br    };
32314089Sodanrc@yahoo.com.br
32414089Sodanrc@yahoo.com.br    /**
32514089Sodanrc@yahoo.com.br     * Get the index of the dictionary match location.
32614089Sodanrc@yahoo.com.br     *
32714089Sodanrc@yahoo.com.br     * @return The index of the match location.
32814089Sodanrc@yahoo.com.br     */
32914089Sodanrc@yahoo.com.br    uint8_t getMatchLocation() const { return matchLocation; }
33014089Sodanrc@yahoo.com.br
33114089Sodanrc@yahoo.com.br    /**
33214089Sodanrc@yahoo.com.br     * Get size, in bits, of the pattern (excluding prefix). Corresponds to
33314089Sodanrc@yahoo.com.br     * unmatched_data_size + code_length.
33414089Sodanrc@yahoo.com.br     *
33514089Sodanrc@yahoo.com.br     * @return The size.
33614089Sodanrc@yahoo.com.br     */
33714089Sodanrc@yahoo.com.br    std::size_t getSizeBits() const {
33814089Sodanrc@yahoo.com.br        return numUnmatchedBytes*CHAR_BIT + length;
33914089Sodanrc@yahoo.com.br    }
34014089Sodanrc@yahoo.com.br
34114089Sodanrc@yahoo.com.br    /**
34214089Sodanrc@yahoo.com.br     * Determine if pattern allocates a dictionary entry.
34314089Sodanrc@yahoo.com.br     *
34414089Sodanrc@yahoo.com.br     * @return True if should allocate a dictionary entry.
34514089Sodanrc@yahoo.com.br     */
34614089Sodanrc@yahoo.com.br    bool shouldAllocate() const {
34714089Sodanrc@yahoo.com.br        return allocate;
34814089Sodanrc@yahoo.com.br    }
34914089Sodanrc@yahoo.com.br
35014089Sodanrc@yahoo.com.br    std::string print() const {
35114089Sodanrc@yahoo.com.br        return csprintf("pattern %s (encoding %x, size %u bits)",
35214089Sodanrc@yahoo.com.br                        getName(patternNumber), getCode(), getSizeBits());
35314089Sodanrc@yahoo.com.br    }
35414089Sodanrc@yahoo.com.br
35514089Sodanrc@yahoo.com.br    /**
35614089Sodanrc@yahoo.com.br     * Decompress the pattern. Each pattern has its own way of interpreting
35714089Sodanrc@yahoo.com.br     * its data.
35814089Sodanrc@yahoo.com.br     *
35914089Sodanrc@yahoo.com.br     * @param dict_bytes The bytes in the corresponding matching entry.
36014089Sodanrc@yahoo.com.br     * @param data The decompressed pattern.
36114089Sodanrc@yahoo.com.br     * @return Whether entry should be added to dictionary or not.
36214089Sodanrc@yahoo.com.br     */
36314089Sodanrc@yahoo.com.br    virtual bool decompress(const std::array<uint8_t, 4> dict_bytes,
36414089Sodanrc@yahoo.com.br                            std::array<uint8_t, 4>& data) const = 0;
36514089Sodanrc@yahoo.com.br};
36614089Sodanrc@yahoo.com.br
36714089Sodanrc@yahoo.com.brclass CPack::PatternZZZZ : public Pattern
36814089Sodanrc@yahoo.com.br{
36914089Sodanrc@yahoo.com.br  public:
37014089Sodanrc@yahoo.com.br    PatternZZZZ(const std::array<uint8_t, 4> bytes, const int match_location)
37114089Sodanrc@yahoo.com.br        : Pattern(ZZZZ, 0x0, 2, 0, 0, false) {}
37214089Sodanrc@yahoo.com.br
37314089Sodanrc@yahoo.com.br    static bool isPattern(const std::array<uint8_t, 4>& bytes,
37414089Sodanrc@yahoo.com.br                          const std::array<uint8_t, 4>& dict_bytes,
37514089Sodanrc@yahoo.com.br                          const int match_location)
37614089Sodanrc@yahoo.com.br    {
37714089Sodanrc@yahoo.com.br        return (bytes[3] == 0) && (bytes[2] == 0) && (bytes[1] == 0) &&
37814089Sodanrc@yahoo.com.br               (bytes[0] == 0);
37914089Sodanrc@yahoo.com.br    }
38014089Sodanrc@yahoo.com.br
38114089Sodanrc@yahoo.com.br    bool decompress(const std::array<uint8_t, 4> dict_bytes,
38214089Sodanrc@yahoo.com.br                    std::array<uint8_t, 4>& data) const override
38314089Sodanrc@yahoo.com.br    {
38414089Sodanrc@yahoo.com.br        data = {0, 0, 0, 0};
38514089Sodanrc@yahoo.com.br        return false;
38614089Sodanrc@yahoo.com.br    }
38714089Sodanrc@yahoo.com.br};
38814089Sodanrc@yahoo.com.br
38914089Sodanrc@yahoo.com.brclass CPack::PatternXXXX : public Pattern
39014089Sodanrc@yahoo.com.br{
39114089Sodanrc@yahoo.com.br  private:
39214089Sodanrc@yahoo.com.br    /**
39314089Sodanrc@yahoo.com.br     * A copy of the word.
39414089Sodanrc@yahoo.com.br     */
39514089Sodanrc@yahoo.com.br    const std::array<uint8_t, 4> bytes;
39614089Sodanrc@yahoo.com.br
39714089Sodanrc@yahoo.com.br  public:
39814089Sodanrc@yahoo.com.br    PatternXXXX(const std::array<uint8_t, 4> bytes, const int match_location)
39914089Sodanrc@yahoo.com.br        : Pattern(XXXX, 0x1, 2, 4, 0, true), bytes(bytes) {}
40014089Sodanrc@yahoo.com.br
40114089Sodanrc@yahoo.com.br    static bool isPattern(const std::array<uint8_t, 4>& bytes,
40214089Sodanrc@yahoo.com.br                          const std::array<uint8_t, 4>& dict_bytes,
40314089Sodanrc@yahoo.com.br                          const int match_location)
40414089Sodanrc@yahoo.com.br    {
40514089Sodanrc@yahoo.com.br        // It can always be an unmatch, as it is set to this class when other
40614089Sodanrc@yahoo.com.br        // patterns fail
40714089Sodanrc@yahoo.com.br        return true;
40814089Sodanrc@yahoo.com.br    }
40914089Sodanrc@yahoo.com.br
41014089Sodanrc@yahoo.com.br    bool decompress(const std::array<uint8_t, 4> dict_bytes,
41114089Sodanrc@yahoo.com.br                    std::array<uint8_t, 4>& data) const override
41214089Sodanrc@yahoo.com.br    {
41314089Sodanrc@yahoo.com.br        data = bytes;
41414089Sodanrc@yahoo.com.br        return true;
41514089Sodanrc@yahoo.com.br    }
41614089Sodanrc@yahoo.com.br};
41714089Sodanrc@yahoo.com.br
41814089Sodanrc@yahoo.com.brclass CPack::PatternMMMM : public Pattern
41914089Sodanrc@yahoo.com.br{
42014089Sodanrc@yahoo.com.br  public:
42114089Sodanrc@yahoo.com.br    PatternMMMM(const std::array<uint8_t, 4> bytes, const int match_location)
42214089Sodanrc@yahoo.com.br        : Pattern(MMMM, 0x2, 6, 0, match_location, true) {}
42314089Sodanrc@yahoo.com.br
42414089Sodanrc@yahoo.com.br    static bool isPattern(const std::array<uint8_t, 4>& bytes,
42514089Sodanrc@yahoo.com.br                          const std::array<uint8_t, 4>& dict_bytes,
42614089Sodanrc@yahoo.com.br                          const int match_location)
42714089Sodanrc@yahoo.com.br    {
42814089Sodanrc@yahoo.com.br        return (bytes == dict_bytes) && (match_location >= 0);
42914089Sodanrc@yahoo.com.br    }
43014089Sodanrc@yahoo.com.br
43114089Sodanrc@yahoo.com.br    bool decompress(const std::array<uint8_t, 4> dict_bytes,
43214089Sodanrc@yahoo.com.br                    std::array<uint8_t, 4>& data) const override
43314089Sodanrc@yahoo.com.br    {
43414089Sodanrc@yahoo.com.br        data = dict_bytes;
43514089Sodanrc@yahoo.com.br        return true;
43614089Sodanrc@yahoo.com.br    }
43714089Sodanrc@yahoo.com.br};
43814089Sodanrc@yahoo.com.br
43914089Sodanrc@yahoo.com.brclass CPack::PatternMMXX : public Pattern
44014089Sodanrc@yahoo.com.br{
44114089Sodanrc@yahoo.com.br  private:
44214089Sodanrc@yahoo.com.br    /**
44314089Sodanrc@yahoo.com.br     * A copy of the unmatched bytes.
44414089Sodanrc@yahoo.com.br     */
44514089Sodanrc@yahoo.com.br    const uint8_t byte0;
44614089Sodanrc@yahoo.com.br    const uint8_t byte1;
44714089Sodanrc@yahoo.com.br
44814089Sodanrc@yahoo.com.br  public:
44914089Sodanrc@yahoo.com.br    PatternMMXX(const std::array<uint8_t, 4> bytes, const int match_location)
45014089Sodanrc@yahoo.com.br        : Pattern(MMXX, 0xC, 8, 2, match_location, true),
45114089Sodanrc@yahoo.com.br                  byte0(bytes[0]), byte1(bytes[1]) {}
45214089Sodanrc@yahoo.com.br
45314089Sodanrc@yahoo.com.br    static bool isPattern(const std::array<uint8_t, 4>& bytes,
45414089Sodanrc@yahoo.com.br                          const std::array<uint8_t, 4>& dict_bytes,
45514089Sodanrc@yahoo.com.br                          const int match_location)
45614089Sodanrc@yahoo.com.br    {
45714089Sodanrc@yahoo.com.br        // Notice we don't compare bytes[0], as otherwise we'd be unnecessarily
45814089Sodanrc@yahoo.com.br        // discarding MMXM. If that pattern is added this should be modified
45914089Sodanrc@yahoo.com.br        return (bytes[3] == dict_bytes[3]) && (bytes[2] == dict_bytes[2]) &&
46014089Sodanrc@yahoo.com.br               (bytes[1] != dict_bytes[1]) && (match_location >= 0);
46114089Sodanrc@yahoo.com.br
46214089Sodanrc@yahoo.com.br    }
46314089Sodanrc@yahoo.com.br
46414089Sodanrc@yahoo.com.br    bool decompress(const std::array<uint8_t, 4> dict_bytes,
46514089Sodanrc@yahoo.com.br                    std::array<uint8_t, 4>& data) const override
46614089Sodanrc@yahoo.com.br    {
46714089Sodanrc@yahoo.com.br        data = {byte0, byte1, dict_bytes[2], dict_bytes[3]};
46814089Sodanrc@yahoo.com.br        return true;
46914089Sodanrc@yahoo.com.br    }
47014089Sodanrc@yahoo.com.br};
47114089Sodanrc@yahoo.com.br
47214089Sodanrc@yahoo.com.brclass CPack::PatternZZZX : public Pattern
47314089Sodanrc@yahoo.com.br{
47414089Sodanrc@yahoo.com.br  private:
47514089Sodanrc@yahoo.com.br    /**
47614089Sodanrc@yahoo.com.br     * A copy of the unmatched byte.
47714089Sodanrc@yahoo.com.br     */
47814089Sodanrc@yahoo.com.br    const uint8_t byte;
47914089Sodanrc@yahoo.com.br
48014089Sodanrc@yahoo.com.br  public:
48114089Sodanrc@yahoo.com.br    PatternZZZX(const std::array<uint8_t, 4> bytes, const int match_location)
48214089Sodanrc@yahoo.com.br        : Pattern(ZZZX, 0xD, 4, 1, 0, false), byte(bytes[0]) {}
48314089Sodanrc@yahoo.com.br
48414089Sodanrc@yahoo.com.br    static bool isPattern(const std::array<uint8_t, 4>& bytes,
48514089Sodanrc@yahoo.com.br                          const std::array<uint8_t, 4>& dict_bytes,
48614089Sodanrc@yahoo.com.br                          const int match_location)
48714089Sodanrc@yahoo.com.br    {
48814089Sodanrc@yahoo.com.br        return (bytes[3] == 0) && (bytes[2] == 0) && (bytes[1] == 0) &&
48914089Sodanrc@yahoo.com.br               (bytes[0] != 0);
49014089Sodanrc@yahoo.com.br    }
49114089Sodanrc@yahoo.com.br
49214089Sodanrc@yahoo.com.br    bool decompress(const std::array<uint8_t, 4> dict_bytes,
49314089Sodanrc@yahoo.com.br                    std::array<uint8_t, 4>& data) const override
49414089Sodanrc@yahoo.com.br    {
49514089Sodanrc@yahoo.com.br        data = {byte, 0, 0, 0};
49614089Sodanrc@yahoo.com.br        return false;
49714089Sodanrc@yahoo.com.br    }
49814089Sodanrc@yahoo.com.br};
49914089Sodanrc@yahoo.com.br
50014089Sodanrc@yahoo.com.brclass CPack::PatternMMMX : public Pattern
50114089Sodanrc@yahoo.com.br{
50214089Sodanrc@yahoo.com.br  private:
50314089Sodanrc@yahoo.com.br    /**
50414089Sodanrc@yahoo.com.br     * A copy of the unmatched byte.
50514089Sodanrc@yahoo.com.br     */
50614089Sodanrc@yahoo.com.br    const uint8_t byte;
50714089Sodanrc@yahoo.com.br
50814089Sodanrc@yahoo.com.br  public:
50914089Sodanrc@yahoo.com.br    PatternMMMX(const std::array<uint8_t, 4> bytes, const int match_location)
51014089Sodanrc@yahoo.com.br        : Pattern(MMMX, 0xE, 8, 1, match_location, true),
51114089Sodanrc@yahoo.com.br                  byte(bytes[0]) {}
51214089Sodanrc@yahoo.com.br
51314089Sodanrc@yahoo.com.br    static bool isPattern(const std::array<uint8_t, 4>& bytes,
51414089Sodanrc@yahoo.com.br                          const std::array<uint8_t, 4>& dict_bytes,
51514089Sodanrc@yahoo.com.br                          const int match_location)
51614089Sodanrc@yahoo.com.br    {
51714089Sodanrc@yahoo.com.br        return (bytes[3] == dict_bytes[3]) && (bytes[2] == dict_bytes[2]) &&
51814089Sodanrc@yahoo.com.br               (bytes[1] == dict_bytes[1]) && (bytes[0] != dict_bytes[0]) &&
51914089Sodanrc@yahoo.com.br               (match_location >= 0);
52014089Sodanrc@yahoo.com.br    }
52114089Sodanrc@yahoo.com.br
52214089Sodanrc@yahoo.com.br    bool decompress(const std::array<uint8_t, 4> dict_bytes,
52314089Sodanrc@yahoo.com.br                    std::array<uint8_t, 4>& data) const override
52414089Sodanrc@yahoo.com.br    {
52514089Sodanrc@yahoo.com.br        data = {byte, dict_bytes[1], dict_bytes[2], dict_bytes[3]};
52614089Sodanrc@yahoo.com.br        return true;
52714089Sodanrc@yahoo.com.br    }
52814089Sodanrc@yahoo.com.br};
52914089Sodanrc@yahoo.com.br
53014089Sodanrc@yahoo.com.brclass CPack::CompData : public CompressionData
53114089Sodanrc@yahoo.com.br{
53214089Sodanrc@yahoo.com.br  public:
53314089Sodanrc@yahoo.com.br    /**
53414089Sodanrc@yahoo.com.br     * The patterns matched in the original line.
53514089Sodanrc@yahoo.com.br     */
53614089Sodanrc@yahoo.com.br    std::vector<std::unique_ptr<Pattern>> entries;
53714089Sodanrc@yahoo.com.br
53814089Sodanrc@yahoo.com.br    /**
53914089Sodanrc@yahoo.com.br     * Default constructor.
54014089Sodanrc@yahoo.com.br     *
54114089Sodanrc@yahoo.com.br     * @param dictionary_size Number of entries in the dictionary.
54214089Sodanrc@yahoo.com.br     */
54314089Sodanrc@yahoo.com.br    CompData(const std::size_t dictionary_size);
54414089Sodanrc@yahoo.com.br
54514089Sodanrc@yahoo.com.br    /**
54614089Sodanrc@yahoo.com.br     * Default destructor.
54714089Sodanrc@yahoo.com.br     */
54814089Sodanrc@yahoo.com.br    ~CompData();
54914089Sodanrc@yahoo.com.br};
55014089Sodanrc@yahoo.com.br
55114089Sodanrc@yahoo.com.br#endif //__MEM_CACHE_COMPRESSORS_CPACK_HH__
552