gso.h

Go to the documentation of this file.

/* Copyright (C) 2005-2008 Damien Stehle.
   Copyright (C) 2007 David Cade.
   Copyright (C) 2011 Xavier Pujol.
 
   This file is part of fplll. fplll is free software: you
   can redistribute it and/or modify it under the terms of the GNU Lesser
   General Public License as published by the Free Software Foundation,
   either version 2.1 of the License, or (at your option) any later version.
 
   fplll is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
   GNU Lesser General Public License for more details.
 
   You should have received a copy of the GNU Lesser General Public License
   along with fplll. If not, see <http://www.gnu.org/licenses/>. */
 
#ifndef FPLLL_GSO_H
#define FPLLL_GSO_H
 
#include "gso_interface.h"
#include "nr/matrix.h"
#include "util.h"
 
FPLLL_BEGIN_NAMESPACE
 
template <class ZT, class FT> class MatGSO : public MatGSOInterface<ZT, FT>
{
public:
  using MatGSOInterface<ZT, FT>::d;
  using MatGSOInterface<ZT, FT>::n_known_rows;
  using MatGSOInterface<ZT, FT>::n_source_rows;
  using MatGSOInterface<ZT, FT>::u;
  using MatGSOInterface<ZT, FT>::enable_transform;
  using MatGSOInterface<ZT, FT>::cols_locked;  // maybe scratch.
  using MatGSOInterface<ZT, FT>::enable_int_gram;
  using MatGSOInterface<ZT, FT>::gso_valid_cols;
  using MatGSOInterface<ZT, FT>::enable_inverse_transform;
  using MatGSOInterface<ZT, FT>::u_inv_t;
  using MatGSOInterface<ZT, FT>::sym_g;
  using MatGSOInterface<ZT, FT>::mu;
  using MatGSOInterface<ZT, FT>::r;
  using MatGSOInterface<ZT, FT>::ztmp1;
  using MatGSOInterface<ZT, FT>::ztmp2;
  using MatGSOInterface<ZT, FT>::row_op_force_long;
  using MatGSOInterface<ZT, FT>::alloc_dim;
  using MatGSOInterface<ZT, FT>::get_mu;
  using MatGSOInterface<ZT, FT>::get_r;
  using MatGSOInterface<ZT, FT>::gptr;
  using MatGSOInterface<ZT, FT>::invalidate_gso_row;
  using MatGSOInterface<ZT, FT>::gf;
  using MatGSOInterface<ZT, FT>::bf;
  using MatGSOInterface<ZT, FT>::discover_all_rows;
  using MatGSOInterface<ZT, FT>::init_row_size;
  using MatGSOInterface<ZT, FT>::enable_row_expo;
  using MatGSOInterface<ZT, FT>::row_expo;
  using MatGSOInterface<ZT, FT>::n_known_cols;
  using MatGSOInterface<ZT, FT>::tmp_col_expo;
 
  using MatGSOInterface<ZT, FT>::remove_last_row;
  using MatGSOInterface<ZT, FT>::print_mu_r_g;
  using MatGSOInterface<ZT, FT>::update_gso;
  using MatGSOInterface<ZT, FT>::update_gso_row;
  using MatGSOInterface<ZT, FT>::row_addmul;
  using MatGSOInterface<ZT, FT>::symmetrize_g;
 
#ifdef DEBUG
  /* Used only in debug mode. */
  using MatGSOInterface<ZT, FT>::row_op_first;
  using MatGSOInterface<ZT, FT>::row_op_last;
  using MatGSOInterface<ZT, FT>::in_row_op_range;
#endif
 
  MatGSO(Matrix<ZT> &arg_b, Matrix<ZT> &arg_u, Matrix<ZT> &arg_uinv_t, int flags)
      : MatGSOInterface<ZT, FT>(arg_u, arg_uinv_t, flags), b(arg_b)
  {
    FPLLL_DEBUG_CHECK(!(enable_int_gram && enable_row_expo));
    d = b.get_rows();
    if (enable_row_expo)
    {
      tmp_col_expo.resize(b.get_cols());
    }
    if (enable_int_gram)
    {
      gptr = &g;
    }
    size_increased();
#ifdef DEBUG
    row_op_first = row_op_last = -1;
#endif
  }
 
public:
  Matrix<ZT> &b;
  Matrix<ZT> g;
 
  virtual inline ZT &sqnorm_coordinates(ZT &sqnorm, vector<ZT> coordinates);
 
  virtual inline long get_max_exp_of_b();
  virtual inline bool b_row_is_zero(int i);
  virtual inline int get_cols_of_b() const;
  virtual inline int get_rows_of_b() const;
  virtual inline void negate_row_of_b(int i);
 
  virtual inline void create_rows(int n_new_rows);
  virtual inline void remove_last_rows(int n_removed_rows);
 
  virtual void move_row(int old_r, int new_r);
 
  // --> moved to interface
  // virtual inline void row_addmul(int i, int j, const FT &x);
 
  virtual void row_addmul_we(int i, int j, const FT &x, long expo_add);
 
  // b[i] += b[j] / b[i] -= b[j] (i > j)
  virtual void row_add(int i, int j);
  virtual void row_sub(int i, int j);
 
  //  virtual inline void printparam(ostream &os);
  virtual inline FT &get_gram(FT &f, int i, int j);
 
  virtual inline ZT &get_int_gram(ZT &z, int i, int j);
 
  // b[i] <-> b[j] (i < j)
  virtual void row_swap(int i, int j);
 
  void to_canonical(vector<FT> &w, const vector<FT> &v, long start = 0);
 
  void from_canonical(vector<FT> &v, const vector<FT> &w, long start = 0, long dimension = -1);
 
  void virtual babai(vector<ZT> &v, int start = 0, int dimension = -1, bool gso = false);
 
  void virtual babai(vector<ZT> &w, const vector<FT> &v, int start = 0, int dimension = -1,
                     bool gso = false);
 
private:
  /* Allocates matrices and arrays whose size depends on d (all but tmp_col_expo).
   When enable_int_gram=false, initializes bf. */
  virtual void size_increased();
 
  virtual void discover_row();
 
  /* Upates the i-th row of bf. It does not invalidate anything, so the caller
     must take into account that it might change row_expo. */
  virtual void update_bf(int i);
  /* Marks g(i, j) for all j <= i (but NOT for j > i) */
  virtual void invalidate_gram_row(int i);
 
  // b[i] <- b[i] + x * b[j] (i > j)
  virtual void row_addmul_si(int i, int j, long x);
  // b[i] <- b[i] + (2^expo * x) * b[j] (i > j)
  virtual void row_addmul_si_2exp(int i, int j, long x, long expo);
  virtual void row_addmul_2exp(int i, int j, const ZT &x, long expo);
};
 
template <class ZT, class FT>
inline ZT &MatGSO<ZT, FT>::sqnorm_coordinates(ZT &sqnorm, vector<ZT> coordinates)
{
  vector<ZT> tmpvec;
  ZT tmp;
  sqnorm = 0;
  vector_matrix_product(tmpvec, coordinates, b);
  for (size_t j = 0; j < tmpvec.size(); j++)
  {
    tmp.mul(tmpvec[j], tmpvec[j]);
    sqnorm.add(sqnorm, tmp);
  }
  return sqnorm;
}
 
template <class ZT, class FT> inline long MatGSO<ZT, FT>::get_max_exp_of_b()
{
  return b.get_max_exp();
}
 
template <class ZT, class FT> inline bool MatGSO<ZT, FT>::b_row_is_zero(int i)
{
  return b[i].is_zero();
}
template <class ZT, class FT> inline int MatGSO<ZT, FT>::get_cols_of_b() const
{
  return b.get_cols();
}
 
template <class ZT, class FT> inline int MatGSO<ZT, FT>::get_rows_of_b() const
{
  return b.get_rows();
}
 
template <class ZT, class FT> inline void MatGSO<ZT, FT>::negate_row_of_b(int i)
{
 
  for (int j = 0; j < get_cols_of_b(); j++)
  {
    b[i][j].neg(b[i][j]);
  }
  if (enable_int_gram)
  {
    for (int j = 0; j < get_rows_of_b(); j++)
    {
      if (j < i)
      {
        g(i, j).neg(g(i, j));
      }
      else if (j > i)
      {
        g(j, i).neg(g(j, i));
      }
    }
  }
}
 
template <class ZT, class FT> inline FT &MatGSO<ZT, FT>::get_gram(FT &f, int i, int j)
{
  FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j <= i && j < n_source_rows &&
                    !in_row_op_range(i));
  if (enable_int_gram)
  {
    f.set_z(g(i, j));
  }
  else
  {
    if (gf(i, j).is_nan())
    {
      bf[i].dot_product(gf(i, j), bf[j], n_known_cols);
    }
    f = gf(i, j);
  }
  return f;
}
 
template <class ZT, class FT> inline ZT &MatGSO<ZT, FT>::get_int_gram(ZT &z, int i, int j)
{
  FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j <= i && j < n_source_rows &&
                    !in_row_op_range(i));
  if (enable_int_gram)
  {
    z = g(i, j);
  }
  else
  {
 
    b[i].dot_product(z, b[j], n_known_cols);
  }
  return z;
}
 
template <class ZT, class FT> inline void MatGSO<ZT, FT>::create_rows(int n_new_rows)
{
  FPLLL_DEBUG_CHECK(!cols_locked);
  int old_d = d;
  d += n_new_rows;
  b.set_rows(d);
  for (int i = old_d; i < d; i++)
  {
    for (int j = 0; j < b.get_cols(); j++)
    {
      b[i][j] = 0;
    }
  }
  if (enable_transform)
  {
    u.set_rows(d);
    for (int i = old_d; i < d; i++)
      for (int j = 0; j < u.get_cols(); j++)
        u[i][j] = 0;
  }
  size_increased();
  if (n_known_rows == old_d)
    discover_all_rows();
}
 
template <class ZT, class FT> inline void MatGSO<ZT, FT>::remove_last_rows(int n_removed_rows)
{
  FPLLL_DEBUG_CHECK(!cols_locked && d >= n_removed_rows);
  d -= n_removed_rows;
  n_known_rows  = min(n_known_rows, d);
  n_source_rows = n_known_rows;
  b.set_rows(d);
  if (enable_transform)
    u.set_rows(d);
}
 
FPLLL_END_NAMESPACE
 
#endif