text: /*
   * Copyright (c) 2018-2019 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.
   */
  
  /** @file
   * Implementation of a dictionary based cache compressor.
   */
  
  #ifndef __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_IMPL_HH__
  #define __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_IMPL_HH__
  
  #include <algorithm>
  
  #include "debug/CacheComp.hh"
  #include "mem/cache/compressors/dictionary_compressor.hh"
  #include "params/BaseDictionaryCompressor.hh"
  
  template <class T>
  DictionaryCompressor<T>::CompData::CompData()
      : CompressionData()
  {
  }
  
  template <class T>
  void
  DictionaryCompressor<T>::CompData::addEntry(std::unique_ptr<Pattern> pattern)
  {
      // Increase size
      setSizeBits(getSizeBits() + pattern->getSizeBits());
  
      // Push new entry to list
      entries.push_back(std::move(pattern));
  }
  
  template <class T>
  DictionaryCompressor<T>::DictionaryCompressor(const Params *p)
      : BaseDictionaryCompressor(p)
  {
      dictionary.resize(dictionarySize);
  
      resetDictionary();
  }
  
  template <class T>
  void
  DictionaryCompressor<T>::resetDictionary()
  {
      // Reset number of valid entries
      numEntries = 0;
  
      // Set all entries as 0
      std::fill(dictionary.begin(), dictionary.end(), toDictionaryEntry(0));
  }
  
  template <typename T>
  std::unique_ptr<typename DictionaryCompressor<T>::Pattern>
  DictionaryCompressor<T>::compressValue(const T data)
  {
      // Split data in bytes
      const DictionaryEntry bytes = toDictionaryEntry(data);
  
      // Start as a no-match pattern. A negative match location is used so that
      // patterns that depend on the dictionary entry don't match
      std::unique_ptr<Pattern> pattern =
          getPattern(bytes, toDictionaryEntry(0), -1);
  
      // Search for word on dictionary
      for (std::size_t i = 0; i < numEntries; i++) {
          // Try matching input with possible patterns
          std::unique_ptr<Pattern> temp_pattern =
              getPattern(bytes, dictionary[i], i);
  
          // Check if found pattern is better than previous
          if (temp_pattern->getSizeBits() < pattern->getSizeBits()) {
              pattern = std::move(temp_pattern);
          }
      }
  
      // Update stats
      patternStats[pattern->getPatternNumber()]++;
  
      // Push into dictionary
      if (pattern->shouldAllocate()) {
          addToDictionary(bytes);
      }
  
      return pattern;
  }
  
  template <class T>
  std::unique_ptr<BaseCacheCompressor::CompressionData>
  DictionaryCompressor<T>::compress(const uint64_t* data)
  {
      std::unique_ptr<BaseCacheCompressor::CompressionData> comp_data =
          std::unique_ptr<CompData>(new CompData());
  
      // Reset dictionary
      resetDictionary();
  
      // Compress every value sequentially
      CompData* const comp_data_ptr = static_cast<CompData*>(comp_data.get());
      const std::vector<T> values((T*)data, (T*)data + blkSize / sizeof(T));
      for (const auto& value : values) {
          std::unique_ptr<Pattern> pattern = compressValue(value);
          DPRINTF(CacheComp, "Compressed %016x to %s\n", value,
              pattern->print());
          comp_data_ptr->addEntry(std::move(pattern));
      }
  
      // Return compressed line
      return comp_data;
  }
  
  template <class T>
  T
  DictionaryCompressor<T>::decompressValue(const Pattern* pattern)
  {
      // Search for matching entry
      auto entry_it = dictionary.begin();
      std::advance(entry_it, pattern->getMatchLocation());
  
      // Decompress the match. If the decompressed value must be added to
      // the dictionary, do it
      const DictionaryEntry data = pattern->decompress(*entry_it);
      if (pattern->shouldAllocate()) {
          addToDictionary(data);
      }
  
      // Return value
      return fromDictionaryEntry(data);
  }
  
  template <class T>
  void
  DictionaryCompressor<T>::decompress(const CompressionData* comp_data,
      uint64_t* data)
  {
      const CompData* casted_comp_data = static_cast<const CompData*>(comp_data);
  
      // Reset dictionary
      resetDictionary();
  
      // Decompress every entry sequentially
      std::vector<T> decomp_values;
      for (const auto& entry : casted_comp_data->entries) {
          const T value = decompressValue(&*entry);
          decomp_values.push_back(value);
          DPRINTF(CacheComp, "Decompressed %s to %x\n", entry->print(), value);
      }
  
      // Concatenate the decompressed values to generate the original data
      for (std::size_t i = 0; i < blkSize/8; i++) {
          data[i] = 0;
          const std::size_t values_per_entry = sizeof(uint64_t)/sizeof(T);
          for (int j = values_per_entry - 1; j >= 0; j--) {
              data[i] |=
                  static_cast<uint64_t>(decomp_values[values_per_entry*i+j]) <<
                  (j*8*sizeof(T));
          }
      }
  }
  
  template <class T>
  typename DictionaryCompressor<T>::DictionaryEntry
  DictionaryCompressor<T>::toDictionaryEntry(T value)
  {
      DictionaryEntry entry;
      for (int i = 0; i < sizeof(T); i++) {
          entry[i] = value & 0xFF;
          value >>= 8;
      }
      return entry;
  }
  
  template <class T>
  T
  DictionaryCompressor<T>::fromDictionaryEntry(const DictionaryEntry& entry)
  {
      T value = 0;
      for (int i = sizeof(T) - 1; i >= 0; i--) {
          value <<= 8;
          value |= entry[i];
      }
      return value;
  }
  
  #endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_IMPL_HH__
  