/*
   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 programme prints an array for each (odd prime) base.
    The array defines which values of the single lsd of N in this base mean the higher level reduction ratio (series B)
    and which the lower rr (series A) in a filter using LSDs of the big presquare.

    It also checks the following conjectures and halts with an error message if one fails:

    1. For each prime base (except 2), there are exactly two different reduction ratios for a filter using one LSD.
    2. There are equal numbers of LSD values of N causing each series.
    (Value 0 is not considered a possible lsd, since that would mean N was a multiple of the small prime base)
    3. The number of stop patterns for a filter with 1 LSD is
       stops = (base - 1)/2 for series A
       stops = (base + 1)/2 for series B
       So for example for base 7, there are:
           3 stop patterns (ie big presquare LSD values) in series A
           4 stop patterns (ie big presquare LSD values) in series B
       - note this means they always sum to base.

   Files needed are this one (lsd.cc), stop.cc and stop.h

   On GNU/Linux it has been built with

   g++  lsd.cc stop.cc -o lsd

   and run with no arguments:

~ # ./lsd 
"xx", // 2
"xAB", // 3
"xABBA", // 5
"xAABABB", // 7
...

*/

#include <cstdio>

#define ARRAYSIZE(a) (sizeof a/sizeof a[0])
#include "stop.h"

static const char primes[] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,};

int status_message(int status, const char* message)
{
    fprintf(stderr, "lsd: error %d %s\n", status, message);
    return status;
}

/* base must be prime
   returns non zero on error
*/

int tabulate(unsigned base)
{
    char stop_table[base];
    char valid_squares[base];
    unsigned long base_powers[2]; // needed by fill_stop_table()

    /*
        Every value of lsd is mapped to one of two series.
        (Here "series" refers to the series of reduction ratios that will be obtained as the number of ls digits is increased above 1)
        The function of the following array is to record this mapping, as it is discovered by the code in this function.
        The two series always have a different initial reduction ratio, (initial meaning when considering only the 1st ls digit.)
        This array maps value of lsd (1 to base - 1) (as array position) to a series designation (1 or 2) (as element value).
        Note position 0 is unused, since 0 is not a possible lsd value of N (which is the product of a pair of large primes).
        We will designate as series 1 whichever series the first lsd tested belongs to.
        The other series will be series 2.
        After we have found both series we will see which one has the higher reduction ratio on single lsd.
    */
    unsigned lsd_mapping[base];

    base_powers[0] = 1; // for completeness, probably will never be used: base^0 = 1
    base_powers[1] = base;

    if (2 == base)
        return status_message(75, "internal, base 2 requested, for which this module is not suitable");

    for (unsigned i = 0; i < ARRAYSIZE(valid_squares); i++)
        valid_squares[i] = 0;

    fill_valid_squares(valid_squares, base, 100); // 100 is an arbitrary large number of digits, more than will be used here

    /*
        this code will go through all digit values of N to demonstrate the conjecture
        that both series always have equal numbers of digit values and that all digit values belong to one of the two series.
    */

    for (unsigned i = 0; i < ARRAYSIZE(lsd_mapping); i++)
        lsd_mapping[i] = 0; // 0 means unknown, 1 means series 1, 2 means series 2

    unsigned long series1_stopped_n = 0; // note odd prime base can never have 0 stopped, so 0 is out-of-band value meaning uninitialised
    unsigned long series2_stopped_n = 0;

    unsigned series1_lsd_count = 0; // count of distinct values actually seen going through all lsd values
    unsigned series2_lsd_count = 0;

    for (unsigned long lsd = 1; lsd < base; lsd++)
    {
        fill_stop_table(stop_table, lsd, base_powers, 1, valid_squares, base);
        unsigned long stopped = number_stopped_at_first_digit(stop_table, base);

        if (stopped == series1_stopped_n)
        {
            lsd_mapping[lsd] = 1;
            series1_lsd_count++;
        }
        else if (stopped == series2_stopped_n)
        {
            lsd_mapping[lsd] = 2;
            series2_lsd_count++;
        }
        else
        {
            // must be the first in this loop, in one of the series
            if (!series1_lsd_count)
            {
                series1_stopped_n = stopped;
                lsd_mapping[lsd] = 1;
                series1_lsd_count = 1;
            }
            else if (!series2_lsd_count)
            {
                series2_stopped_n = stopped;
                lsd_mapping[lsd] = 2;
                series2_lsd_count = 1;
            }
            else
                return status_message(200, "conjecture failure: more than two stopped count values");
        }
    }

    if (series1_stopped_n + series2_stopped_n != base)
        return status_message(209, "conjecture failure: stop counts do not sum to base");

    if (series1_lsd_count != series2_lsd_count)
        return status_message(213, "conjecture failure: unequal numbers of LSD values in each series");

    unsigned lower_mark = 1;
    unsigned higher_mark = 2;

    if (series1_stopped_n > series2_stopped_n)
    {
      higher_mark = 1;
      lower_mark = 2;
        if (series1_stopped_n*2 != base + 1)
            return status_message(210, "conjecture failure higher stop count is not (base + 1)/2");
    }
    else if (series2_stopped_n*2 != base + 1)
            return status_message(211, "conjecture failure: higher stop count is not (base + 1)/2");

    putchar('"');
    putchar('x');
    for (unsigned i = 1; i < base; i++)
        putchar(lsd_mapping[i] == higher_mark? 'B': 'A');
    putchar('"');
    printf(", // %u\n", base);

    return 0;
}

int main(int argc, char* argv[])
{
    if (argc != 1)
        return status_message(9, "bad invocation should be ./lsd");

    printf("\"xx\", // 2\n"); // dummy line for base 2
    for (unsigned i = 1; i < ARRAYSIZE(primes); i++)
    {
        int ret;

        ret = tabulate(primes[i]);
        if (ret)
            return ret;
    }
    return 0;
}