/*
   Copyright (C) 2022 Stephen Hewitt, cambridgeclarion.org

   This file is part of a programme to research fast Fermat factorisation algorithms.

   This is free software: you can redistribute it and/or modify
   it under the terms of version 3 of the GNU General Public License as
   published by the Free Software Foundation.

   It 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 General Public License for more details.

   You should have received a copy of the GNU General Public Licence
   along with this programme.  If not, see <https://www.gnu.org/licenses/>.

   A copy of the licence is also available at
   https://www.cambridgeclarion.org/download/GPLv3.txt
   It has the following cryptographic hash
   SHA256 3972dc9744f6499f0f9b2dbf76696f2ae7ad8af9b23dde66d6af86c9dfb36986

*/

/*
    This module contains the stop table construction and square table construction functions
    used in Fermat factorisation algorithms research.

    For more information see the series of articles on cambridgeclarion.org, in particular /60.html
    There are also some details in the comments below.
*/

#include "stop2.h"

/*

    This function fills the passed array @stop_table

    The stop table array depends on a particular N to be factorised and a small integer representing a number base, eg base 3.
    Each element in this array represents by its position in the array a value of the LSDs of a big presquare.
    (in the base in which the table is constructed)
    The number of digits represented is at most the number the array was built for and
    here this function builds it for @pattern_digits_n

    It fills the array such that every element is:

    stop_table[i] = d

    where if i is taken as the value of the k LSDs of of a big presquare candidate
    then d is the lowest value of k for which the candidate for a small square calculated from this big presquare is proven
    not to be a square (proven based on its k LSDs, which are checked in the valid_squares table).

    Any value d more than the number of digits that the table was built for is defined to mean only
    that the value i passes this filter for all numbers of LSDs (k) that this table handles.
    It is not intended to be an actual value.

    The size of the stop_table[] and the size of the valid_squares[] table are the same and are both base^pattern_digits_n

    @base_powers is an array with base_power[0] = 1, base_power[1] = base, base_power[2] = base*base, etc
    The size of passed @base_powers[] that contains these values must be at least @pattern_digits_n + 1
    - one longer than you might think because it contains base^0 at position [0] (which is used elsewhere).

    The @lsds_of_N passed must be N mod base^pattern_digits_n
*/

int fill_stop_table(char* stop_table, unsigned long lsds_of_N, unsigned long base_powers[], unsigned pattern_digits_n, const char* const valid_squares)
{
    unsigned long delta = 1;
    unsigned long square = 0;
    unsigned long patterns_n = base_powers[pattern_digits_n];

    for (unsigned long i = 0; i < patterns_n; i++)
    {
        stop_table[i] = 0;
    }

    // big is the big presquare, regenerate successive squares as we go, alternative would have been an array to store them from before
    for (unsigned big = 0; big < patterns_n; big++)
    {
        unsigned long small_square_candidate;
        if (lsds_of_N > square)
            small_square_candidate = patterns_n + square - lsds_of_N;
        else
            small_square_candidate = square - lsds_of_N;

        unsigned digits_n; // number of digits being considered

        for (digits_n = 1; digits_n <= pattern_digits_n; digits_n++)
        {
            if (!valid_squares[small_square_candidate % base_powers[digits_n]])
                break; /* failed to be a valid small square at this digit length */
        }
        stop_table[big] = digits_n; // if stop_table[big] > pattern_digits_n in this table, it means no stop was detected at this value
        square += delta;
        if (square >= patterns_n)
            square -= patterns_n;

        delta += 2;
        if (delta >= patterns_n)
            delta -= patterns_n;
    }
    return 0;
}

/*
    This function is passed an array @square_table[] of length @length

    It sets square_table[i] = @mark for every position, i, in the array where
    i = a^2 mod length, for any integer a.

    Note this function alters only those elements to which it assigns @mark
*/

void fill_valid_squares(char* square_table, unsigned length, char mark)
{
    unsigned long delta = 1;
    unsigned long square = 0;

    for (unsigned i = 0; i < length; i++)
    {
        square_table[square] = mark;
        square += delta;
        if (square >= length)
            square -= length;

        delta += 2;
        if (delta >= length)
            delta -= length;
    }
}

unsigned long number_stopped_at_first_digit(char* stop_table, unsigned base)
{
    unsigned long stopped = 0;

    for (unsigned long i = 0; i < base; i++)
    {
        if (stop_table[i] == 1)
            stopped++;
    }
    return stopped;
}