Quelle ffgen.c Sprache: C

/* Generate ffdata.{c,h} for finite fields, used in
   finfield.c
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_FF 65536

unsigned char is_prime[MAX_FF + 1];
unsigned char is_ff[MAX_FF + 1];
unsigned      deg[MAX_FF + 1];
unsigned      ch[MAX_FF + 1];
unsigned      num_ff;
unsigned      max_deg;

void make_primes()
{
    unsigned int i, j;
    for (i = 2; i <= MAX_FF; i++)
        is_prime[i] = 1;
    for (i = 2; i * i <= MAX_FF; i++) {
        if (is_prime[i]) {
            for (j = 2 * i; j <= MAX_FF; j += i)
                is_prime[j] = 0;
        }
    }
}

void make_ff()
{
    unsigned int i, j, d;
    for (i = 2; i <= MAX_FF; i++) {
        if (is_prime[i]) {
            for (j = i, d = 1; j <= MAX_FF; j *= i, d++) {
                is_ff[j] = 1;
                deg[j] = d;
                ch[j] = i;
                num_ff++;
            }
            if (d > 0 && d - 1 > max_deg)
                max_deg = d - 1;
        }
    }
}

unsigned int needed_bits(unsigned int x)
{
    if (x == 0)
        return 0;
    return 1 + needed_bits(x >> 1);
}

void emit_code(FILE * dest, int header)
{
    unsigned i, j;
    fprintf(dest, "/* This file has been generated by etc/ffgen.c during build,\n");
    fprintf(dest, " do not edit */\n");
    if (header) {
        fprintf(dest, "#ifndef GAP_FFDATA_H\n");
        fprintf(dest, "#define GAP_FFDATA_H\n");
        fprintf(dest, "\n");
        fprintf(dest, "#include \n");
        fprintf(dest, "\n");
        fprintf(dest, "enum {\n");
        fprintf(dest, " NUM_SHORT_FINITE_FIELDS = %d,\n", num_ff);
        fprintf(dest, " MAXSIZE_GF_INTERNAL = %d,\n", MAX_FF);
        fprintf(dest, " DEGREE_LARGEST_INTERNAL_FF = %d,\n", max_deg);
        fprintf(dest, " FIELD_BITS_FFE = %d,\n", needed_bits(num_ff));
        fprintf(dest, " VAL_BITS_FFE = %d\n", needed_bits(MAX_FF - 1));
        fprintf(dest, "};\n");
        fprintf(dest, "\n");
        fprintf(dest, "extern const uint32_t SizeFF[NUM_SHORT_FINITE_FIELDS+1];\n");
        fprintf(dest, "extern const uint8_t DegrFF[NUM_SHORT_FINITE_FIELDS+1];\n");
        fprintf(dest, "extern const uint32_t CharFF[NUM_SHORT_FINITE_FIELDS+1];\n");
        fprintf(dest, "\n");
        if (num_ff < 65536)
            fprintf(dest, "typedef uint16_t FF;\n");
        else
            fprintf(dest, "typedef uint32_t FF;\n");
        if (MAX_FF <= 65536)
            fprintf(dest, "typedef uint16_t FFV;\n");
        else
            fprintf(dest, "typedef uint32_t FFV;\n");
        fprintf(dest, "\n");
        fprintf(dest, "#endif // GAP_FFDATA_H\n");
    }
    else {
        fprintf(dest, "#include \"ffdata.h\"\n");
        fprintf(dest, "\n");
        fprintf(dest, "/* Entries are ordered by value of p^d; can use binary search\n");
        fprintf(dest, " * to find them. Indices start at 1.\n");
        fprintf(dest, " */\n");
        fprintf(dest, "\n");
        fprintf(dest, "const uint8_t DegrFF[NUM_SHORT_FINITE_FIELDS+1] = {\n");
        fprintf(dest, " %3d,", 0);
        for (i = 0, j = 1; i <= MAX_FF; i++) {
            if (is_ff[i]) {
                fprintf(dest, "%3d,", deg[i]);
                j++;
                j %= 16;
                if (!j)
                    fprintf(dest, "\n ");
            }
        }
        if (j)
            fprintf(dest, "\n");
        fprintf(dest, "};\n");
        fprintf(dest, "\n");
        fprintf(dest, "const uint32_t CharFF[NUM_SHORT_FINITE_FIELDS+1] = {\n");
        fprintf(dest, " %9d,", 0);
        for (i = 0, j = 1; i <= MAX_FF; i++) {
            if (is_ff[i]) {
                fprintf(dest, "%9d,", ch[i]);
                j++;
                j %= 6;
                if (!j)
                    fprintf(dest, "\n ");
            }
        }
        if (j)
            fprintf(dest, "\n");
        fprintf(dest, "};\n");
        fprintf(dest, "\n");
        fprintf(dest, "const uint32_t SizeFF[NUM_SHORT_FINITE_FIELDS+1] = {\n");
        fprintf(dest, " %9d,", 0);
        for (i = 0, j = 1; i <= MAX_FF; i++) {
            if (is_ff[i]) {
                fprintf(dest, "%9d,", i);
                j++;
                j %= 6;
                if (!j)
                    fprintf(dest, "\n ");
            }
        }
        if (j)
            fprintf(dest, "\n");
        fprintf(dest, "};\n");
    }
}

void emit_code_to_file_by_basename(int header, char * basename)
{
    char * filename = malloc(strlen(basename) + 3);
    strcpy(filename, basename);
    strcat(filename, header ? ".h" : ".c");
    FILE * f = fopen(filename, "w");
    if (!f) {
        perror("opening output file");
        exit(EXIT_FAILURE);
    }
    emit_code(f, header);
    fclose(f);
}

int main(int argc, char * argv[])
{
    char * opt = argc > 1 ? argv[1] : NULL;
    make_primes();
    make_ff();
    if (!opt)
        emit_code(stdout, 0);
    else if (!strcmp(opt, "h") || !strcmp(opt, ".h") || !strcmp(opt, "-h"))
        emit_code(stdout, 1);
    else if (!strcmp(opt, "c") || !strcmp(opt, ".c") || !strcmp(opt, "-c"))
        emit_code(stdout, 0);
    else if (!strcmp(opt, "-b") && argc > 2) {
        char * basename = argv[2];
        emit_code_to_file_by_basename(0, basename);
        emit_code_to_file_by_basename(1, basename);
    }
    else {
        fprintf(stderr, "Usage: ffgen [-h|-c|-b basename]\n");
        fprintf(stderr, " -h for header file\n");
        fprintf(stderr, " -c for C source file\n");
        fprintf(stderr,
                " -b basename, makes both as basename.c and basename.h\n");
        return 1;
    }
    return 0;
}

quality78%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.