/*
   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 "stop.h"

/*
    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 ls digits 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.
    But it turns out (demonstrated empirically, not yet proven with maths)
    that the same table will also work for any lesser number of digits.

    The value of each element in this array is an integer which represents the number of ls digits that
    have to be included from the big presquare of this value before it is proven that the resulting candidate for a small square
    could not be a square (based on these digits alone).

    If this value is more than the number of digits that the table was built for, then it means we could never be sure
    (based on this table) that this big presquare would not result in a successful candidate for a small square.

    once a position in the table has been found to be not viable at a certain digit length, then all longer digit lengths at that position
    are also not viable. (should be obvious)

    The size of the stop_table[] and the size of the valid_squares[] table are the same and are both patterns_n
    pattern_digits_n must correspond so patterns_n = base^pattern_digits_n

    The @lsds_of_N passed must be N mod patterns_n
    @base_powers is an array with base_power[0] = 1, base_power[1] = base, base_power[2] = base*base, etc
    The size of @base_powers[]  that contains valid values is at least pattern_digits_n + 1
    - one longer than you might think because it contains base^0 at position [0], which is not used. But a logical arrangement.
*/

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 patterns_n)
{
    unsigned long delta = 1;
    unsigned long square = 0;

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

    // big is the big presquare, regenerate successive squares as we go, alernative 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 (digits_n > 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;
}

/* just mark all the positions in the array where index is a (valid square mod length)
    position is marked by value of @mark
    - note that length does not have to be a power of two for this loop - there is no masking
    See elsewhere for explanation of significance of value of mark for prime vs composite bases.
    Note this alters only elements whose index is valid square.
    If zero or whatever is wanted in other elements, they should be cleared before calling this
*/

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;
}