compression.hpp

#ifndef HAVE_COMPRESSION_HPP
#define HAVE_COMPRESSION_HPP
// Autogenerated - do not edit by hand !
#include "global.hpp"
#include "graph_transform.hpp"  // subset
#include "radix.hpp"            // first_occurance

namespace TMBad {

struct period {
  size_t begin;
  size_t size;
  size_t rep;
};

std::ostream &operator<<(std::ostream &os, const period &x);

template <class T>
struct periodic {
  const std::vector<T> &x;
  size_t max_period_size;
  size_t min_period_rep;
  periodic(const std::vector<T> &x, size_t max_period_size,
           size_t min_period_rep = 2)
      : x(x),
        max_period_size(max_period_size),
        min_period_rep(min_period_rep) {}
  bool test_period(size_t start, size_t p) {
    if (start + (p - 1) + p >= x.size()) return false;
    for (size_t i = 0; i < p; i++) {
      if (x[start + i] != x[start + i + p]) return false;
    }
    return true;
  }
  size_t numrep_period(size_t start, size_t p) {
    size_t n = 1;
    while (test_period(start, p)) {
      n++;
      start += p;
    }
    return n;
  }
  period find_best_period(size_t start) {
    size_t p_best = -1, rep_best = 0;
    for (size_t p = 1; p < max_period_size; p++) {
      size_t rep = numrep_period(start, p);
      if (rep > rep_best) {
        p_best = p;
        rep_best = rep;
        p = p * rep;
      }
    }
    period ans = {start, p_best, rep_best};
    return ans;
  }
  std::vector<period> find_all() {
    std::vector<period> ans;
    for (size_t i = 0; i < x.size();) {
      period result = find_best_period(i);
      if (result.rep >= min_period_rep) {
        ans.push_back(result);
        i += result.size * result.rep;
      } else {
        i++;
      }
    }
    return ans;
  }
};

template <class T>
struct matrix_view {
  const T *x;
  size_t nrow, ncol;
  matrix_view(const T *x, size_t nrow, size_t ncol)
      : x(x), nrow(nrow), ncol(ncol) {}
  T operator()(size_t i, size_t j) const { return x[i + j * nrow]; }
  size_t rows() const { return nrow; }
  size_t cols() const { return ncol; }
  template <class Diff_T>
  std::vector<Diff_T> row_diff(size_t i) {
    size_t nd = (cols() >= 1 ? cols() - 1 : 0);
    std::vector<Diff_T> xd(nd);
    for (size_t j = 1; j < cols(); j++)
      xd[j - 1] = (Diff_T)(*this)(i, j) - (Diff_T)(*this)(i, j - 1);
    return xd;
  }
};

std::vector<period> split_period(global *glob, period p,
                                 size_t max_period_size);

struct compressed_input {
  typedef std::ptrdiff_t ptrdiff_t;

  mutable std::vector<ptrdiff_t> increment_pattern;
  std::vector<Index> which_periodic;
  std::vector<Index> period_sizes;
  std::vector<Index> period_offsets;
  std::vector<ptrdiff_t> period_data;

  Index n, m;
  Index nrep;
  Index np;

  mutable Index counter;
  mutable std::vector<Index> inputs;
  std::vector<Index> input_diff;
  size_t input_size() const;
  void update_increment_pattern() const;

  void increment(Args<> &args) const;

  void decrement(Args<> &args) const;
  void forward_init(Args<> &args) const;
  void reverse_init(Args<> &args);
  void dependencies_intervals(Args<> &args, std::vector<Index> &lower,
                              std::vector<Index> &upper) const;

  size_t max_period_size;

  bool test_period(std::vector<ptrdiff_t> &x, size_t p);

  size_t find_shortest(std::vector<ptrdiff_t> &x);
  compressed_input();
  compressed_input(std::vector<Index> &x, size_t offset, size_t nrow, size_t m,
                   size_t ncol, size_t max_period_size);
};

template <class T1, class T2>
struct compare_types {
  const static bool equal = false;
};
template <class T>
struct compare_types<T, T> {
  const static bool equal = true;
};

void compress(global &glob, size_t max_period_size);
struct StackOp : global::SharedDynamicOperator {
  typedef std::ptrdiff_t ptrdiff_t;
  global::operation_stack opstack;
  compressed_input ci;
  StackOp(global *glob, period p, IndexPair ptr, size_t max_period_size);
  StackOp(const StackOp &x);
  void print(global::print_config cfg);
  Index input_size() const;
  Index output_size() const;
  static const bool have_input_size_output_size = true;
  template <class Type>
  void forward(ForwardArgs<Type> args) {
    ci.forward_init(args);

    size_t opstack_size = opstack.size();
    for (size_t i = 0; i < ci.nrep; i++) {
      for (size_t j = 0; j < opstack_size; j++) {
        opstack[j]->forward_incr(args);
      }
      ci.increment(args);
    }
    if (compare_types<Type, Replay>::equal) {
      compress(*get_glob(), ci.max_period_size);
    }
  }
  void forward(ForwardArgs<Writer> &args);
  template <class Type>
  void reverse(ReverseArgs<Type> args) {
    ci.reverse_init(args);
    size_t opstack_size = opstack.size();
    for (size_t i = 0; i < ci.nrep; i++) {
      ci.decrement(args);

      for (size_t j = opstack_size; j > 0;) {
        j--;
        opstack[j]->reverse_decr(args);
      }
    }
    if (compare_types<Type, Replay>::equal) {
      compress(*get_glob(), ci.max_period_size);
    }
  }
  void reverse(ReverseArgs<Writer> &args);
  void dependencies(Args<> args, Dependencies &dep) const;
  static const bool have_dependencies = true;
  static const bool implicit_dependencies = true;
  static const bool allow_remap = false;
  const char *op_name();
};

template <class T>
void trim(std::vector<T> &v, const T &elt) {
  v.erase(std::remove(v.begin(), v.end(), elt), v.end());
}

template <class T>
struct toposort_remap {
  std::vector<T> &remap;
  T i;
  toposort_remap(std::vector<T> &remap, T i) : remap(remap), i(i) {}
  void operator()(Index k) {
    if (remap[k] >= remap[i]) {
      remap[i] = i;
    }
  }
};

void reorder_sub_expressions(global &glob);

template <class T>
struct temporaries_remap {
  std::vector<T> &remap;
  T i;
  temporaries_remap(std::vector<T> &remap, T i) : remap(remap), i(i) {}
  void operator()(Index k) {
    if (remap[k] == T(-1)) {
      if (i > k + 1) remap[k] = i;
      return;
    }

    remap[k] = k;
  }
};

void reorder_temporaries(global &glob);

template <class T>
struct dfs_add_to_stack {
  std::vector<T> &stack;
  std::vector<bool> &visited;
  std::vector<T> &v2o;
  dfs_add_to_stack(std::vector<T> &stack, std::vector<bool> &visited,
                   std::vector<T> &v2o)
      : stack(stack), visited(visited), v2o(v2o) {}
  void operator()(T var) {
    Index op = v2o[var];
    if (!visited[op]) {
      stack.push_back(op);
      visited[op] = true;
    }
  }
};

void reorder_depth_first(global &glob);

void compress(global &glob, size_t max_period_size = 1024);

}  // namespace TMBad
#endif  // HAVE_COMPRESSION_HPP