<commit_before>/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (C) 2007-2011 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC 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.
 *
 * RELIC 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 RELIC. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of the binary field modulus manipulation.
 *
 * @version $Id$
 * @ingroup fb
 */

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

#include "relic_core.h"
#include "relic_conf.h"
#include "relic_dv.h"
#include "relic_fb.h"
#include "relic_pb.h"
#include "relic_fb_low.h"
#include "relic_error.h"

/*============================================================================*/
/* Private definitions                                                        */
/*============================================================================*/

/**
 * Prime modulus.
 */
static fb_st fb_poly;

/**
 * Trinomial or pentanomial non-zero coefficients.
 */
static int poly_a, poly_b, poly_c;

/**
 * Positions of the non-null coefficients on trinomials and pentanomials.
 */
static int pos_a, pos_b, pos_c;

#if FB_TRC == QUICK || !defined(STRIP)

/**
 * Powers of z with non-zero traces.
 */
static int trc_a, trc_b, trc_c;

/**
 * Find non-zero bits for fast trace computation.
 *
 * @throw ERR_NO_MEMORY if there is no available memory.
 * @throw ERR_INVALID if the polynomial is invalid.
 */
static void find_trace() {
	fb_t t0, t1;
	int counter;

	fb_null(t0);
	fb_null(t1);

	trc_a = trc_b = trc_c = -1;

	TRY {
		fb_new(t0);
		fb_new(t1);

		counter = 0;
		for (int i = 0; i < FB_BITS; i++) {
			fb_zero(t0);
			fb_set_bit(t0, i, 1);
			fb_copy(t1, t0);
			for (int j = 1; j < FB_BITS; j++) {
				fb_sqr(t1, t1);
				fb_add(t0, t0, t1);
			}
			if (!fb_is_zero(t0)) {
				switch (counter) {
					case 0:
						trc_a = i;
						trc_b = trc_c = -1;
						break;
					case 1:
						trc_b = i;
						trc_c = -1;
						break;
					case 2:
						trc_c = i;
						break;
					default:
						THROW(ERR_INVALID);
						break;
				}
				counter++;
			}
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fb_free(t0);
		fb_free(t1);
	}
}

#endif

#if FB_SLV == QUICK || !defined(STRIP)

/**
 * Size of the precomputed table of half-traces.
 */
#define HALF_SIZE		((FB_BITS - 1)/ 2)

/**
 * Table of precomputed half-traces.
 */
static fb_st fb_half[(FB_DIGIT / 8 + 1) * FB_DIGS][16];

/**
 * Precomputes half-traces for z^i with odd i.
 *
 * @throw ERR_NO_MEMORY if there is no available memory.
 */
static void find_solve() {
	int i, j, k, l;
	fb_t t0;

	fb_null(t0);

	TRY {
		fb_new(t0);

		l = 0;
		for (i = 0; i < FB_BITS; i += 8, l++) {
			for (j = 0; j < 16; j++) {
				fb_zero(t0);
				for (k = 0; k < 4; k++) {
					if (j & (1 << k)) {
						fb_set_bit(t0, i + 2 * k + 1, 1);
					}
				}
				fb_copy(fb_half[l][j], t0);
				for (k = 0; k < (FB_BITS - 1) / 2; k++) {
					fb_sqr(fb_half[l][j], fb_half[l][j]);
					fb_sqr(fb_half[l][j], fb_half[l][j]);
					fb_add(fb_half[l][j], fb_half[l][j], t0);
				}
			}
			fb_rsh(fb_half[l][j], fb_half[l][j], 1);
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fb_free(t0);
	}
}

#endif

#if FB_SRT == QUICK || !defined(STRIP)

/**
 * Square root of z.
 */
static fb_st fb_srz;

#ifdef FB_PRECO
/**
 * Multiplication table for the z^(1/2).
 */
static fb_st fb_tab_srz[256];

#endif

/**
 * Precomputes the square root of z.
 */
static void find_srz() {

	fb_set_dig(fb_srz, 2);

	for (int i = 1; i < FB_BITS; i++) {
		fb_sqr(fb_srz, fb_srz);
	}

#ifdef FB_PRECO
	for (int i = 0; i <= 255; i++) {
		fb_mul_dig(fb_tab_srz[i], fb_srz, i);
	}
#endif
}

#endif

#if FB_INV == ITOHT || !defined(STRIP)

/**
 * Maximum number of elements in the addition chain for (FB_BITS - 1).
 */
#define MAX_CHAIN		16

/**
 * Stores an addition chain for (FB_BITS - 1).
 */
static int chain[MAX_CHAIN + 1];

/**
 * Stores the length of the addition chain.
 */
static int chain_len;

#ifdef FB_PRECO

/**
 * Tables for repeated squarings.
 */
fb_st fb_tab_sqr[MAX_CHAIN][(FB_DIGIT / 4) * FB_DIGS][16];

/**
 * Threshold where iterated squaring becomes faster.
 */
int fb_sqr_thres;

/**
 * Threshold where iterated square-root becomes faster.
 */
int fb_sqr_thres;

#endif

/**
 * Finds an addition chain for (FB_BITS - 1).
 */
static void find_chain() {
	int i, j, k, l;

	chain_len = -1;
	for (int i = 0; i < MAX_CHAIN; i++) {
		chain[i] = (i << 8) + i;
	}
	switch (FB_BITS) {
		case 193:
			chain[1] = (1 << 8) + 0;
			chain_len = 8;
			break;
		case 233:
			chain[1] = (1 << 8) + 0;
			chain[3] = (3 << 8) + 0;
			chain[6] = (6 << 8) + 0;
			chain_len = 10;
			break;
		case 251:
			chain[1] = (1 << 8) + 0;
			chain[2] = (2 << 8) + 1;
			chain[4] = (4 << 8) + 3;
			chain[5] = (5 << 8) + 4;
			chain[7] = (7 << 8) + 6;
			chain[8] = (8 << 8) + 7;
			chain_len = 10;
			break;
		case 353:
			chain[2] = (2 << 8) + 0;
			chain[4] = (4 << 8) + 0;
			chain_len = 10;
			break;
		case 1223:
			chain[1] = (1 << 8) + 0;
			chain[2] = (2 << 8) + 0;
			chain[4] = (4 << 8) + 2;
			chain[5] = (5 << 8) + 4;<commit_msg>Added addition chain for GF(2^367).<commit_after>/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (C) 2007-2011 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC 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.
 *
 * RELIC 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 RELIC. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of the binary field modulus manipulation.
 *
 * @version $Id$
 * @ingroup fb
 */

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

#include "relic_core.h"
#include "relic_conf.h"
#include "relic_dv.h"
#include "relic_fb.h"
#include "relic_pb.h"
#include "relic_fb_low.h"
#include "relic_error.h"

/*============================================================================*/
/* Private definitions                                                        */
/*============================================================================*/

/**
 * Prime modulus.
 */
static fb_st fb_poly;

/**
 * Trinomial or pentanomial non-zero coefficients.
 */
static int poly_a, poly_b, poly_c;

/**
 * Positions of the non-null coefficients on trinomials and pentanomials.
 */
static int pos_a, pos_b, pos_c;

#if FB_TRC == QUICK || !defined(STRIP)

/**
 * Powers of z with non-zero traces.
 */
static int trc_a, trc_b, trc_c;

/**
 * Find non-zero bits for fast trace computation.
 *
 * @throw ERR_NO_MEMORY if there is no available memory.
 * @throw ERR_INVALID if the polynomial is invalid.
 */
static void find_trace() {
	fb_t t0, t1;
	int counter;

	fb_null(t0);
	fb_null(t1);

	trc_a = trc_b = trc_c = -1;

	TRY {
		fb_new(t0);
		fb_new(t1);

		counter = 0;
		for (int i = 0; i < FB_BITS; i++) {
			fb_zero(t0);
			fb_set_bit(t0, i, 1);
			fb_copy(t1, t0);
			for (int j = 1; j < FB_BITS; j++) {
				fb_sqr(t1, t1);
				fb_add(t0, t0, t1);
			}
			if (!fb_is_zero(t0)) {
				switch (counter) {
					case 0:
						trc_a = i;
						trc_b = trc_c = -1;
						break;
					case 1:
						trc_b = i;
						trc_c = -1;
						break;
					case 2:
						trc_c = i;
						break;
					default:
						THROW(ERR_INVALID);
						break;
				}
				counter++;
			}
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fb_free(t0);
		fb_free(t1);
	}
}

#endif

#if FB_SLV == QUICK || !defined(STRIP)

/**
 * Size of the precomputed table of half-traces.
 */
#define HALF_SIZE		((FB_BITS - 1)/ 2)

/**
 * Table of precomputed half-traces.
 */
static fb_st fb_half[(FB_DIGIT / 8 + 1) * FB_DIGS][16];

/**
 * Precomputes half-traces for z^i with odd i.
 *
 * @throw ERR_NO_MEMORY if there is no available memory.
 */
static void find_solve() {
	int i, j, k, l;
	fb_t t0;

	fb_null(t0);

	TRY {
		fb_new(t0);

		l = 0;
		for (i = 0; i < FB_BITS; i += 8, l++) {
			for (j = 0; j < 16; j++) {
				fb_zero(t0);
				for (k = 0; k < 4; k++) {
					if (j & (1 << k)) {
						fb_set_bit(t0, i + 2 * k + 1, 1);
					}
				}
				fb_copy(fb_half[l][j], t0);
				for (k = 0; k < (FB_BITS - 1) / 2; k++) {
					fb_sqr(fb_half[l][j], fb_half[l][j]);
					fb_sqr(fb_half[l][j], fb_half[l][j]);
					fb_add(fb_half[l][j], fb_half[l][j], t0);
				}
			}
			fb_rsh(fb_half[l][j], fb_half[l][j], 1);
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fb_free(t0);
	}
}

#endif

#if FB_SRT == QUICK || !defined(STRIP)

/**
 * Square root of z.
 */
static fb_st fb_srz;

#ifdef FB_PRECO
/**
 * Multiplication table for the z^(1/2).
 */
static fb_st fb_tab_srz[256];

#endif

/**
 * Precomputes the square root of z.
 */
static void find_srz() {

	fb_set_dig(fb_srz, 2);

	for (int i = 1; i < FB_BITS; i++) {
		fb_sqr(fb_srz, fb_srz);
	}

#ifdef FB_PRECO
	for (int i = 0; i <= 255; i++) {
		fb_mul_dig(fb_tab_srz[i], fb_srz, i);
	}
#endif
}

#endif

#if FB_INV == ITOHT || !defined(STRIP)

/**
 * Maximum number of elements in the addition chain for (FB_BITS - 1).
 */
#define MAX_CHAIN		16

/**
 * Stores an addition chain for (FB_BITS - 1).
 */
static int chain[MAX_CHAIN + 1];

/**
 * Stores the length of the addition chain.
 */
static int chain_len;

#ifdef FB_PRECO

/**
 * Tables for repeated squarings.
 */
fb_st fb_tab_sqr[MAX_CHAIN][(FB_DIGIT / 4) * FB_DIGS][16];

/**
 * Threshold where iterated squaring becomes faster.
 */
int fb_sqr_thres;

/**
 * Threshold where iterated square-root becomes faster.
 */
int fb_sqr_thres;

#endif

/**
 * Finds an addition chain for (FB_BITS - 1).
 */
static void find_chain() {
	int i, j, k, l;

	chain_len = -1;
	for (int i = 0; i < MAX_CHAIN; i++) {
		chain[i] = (i << 8) + i;
	}
	switch (FB_BITS) {
		case 193:
			chain[1] = (1 << 8) + 0;
			chain_len = 8;
			break;
		case 233:
			chain[1] = (1 << 8) + 0;
			chain[3] = (3 << 8) + 0;
			chain[6] = (6 << 8) + 0;
			chain_len = 10;
			break;
		case 251:
			chain[1] = (1 << 8) + 0;
			chain[2] = (2 << 8) + 1;
			chain[4] = (4 << 8) + 3;
			chain[5] = (5 << 8) + 4;
			chain[7] = (7 << 8) + 6;
			chain[8] = (8 << 8) + 7;
			chain_len = 10;
			break;
		case 353:
			chain[2] = (2 << 8) + 0;
			chain[4] = (4 << 8) + 0;
			chain_len = 10;
			break;
		case 367:
			chain[1] = (1 << 8) + 0;
			chain[2] = (2 << 8) + 1;
			chain[6] = (6 << 8) + 3;
			chain[9] = (9 << 8) + 2;
			chain_len = 11;
			break;
		case 1223:
			chain[1] = (1 << 8) + 0;
			chain[2] = (2 << 8) + 0;
			chain[4] = (4 << 8) + 2;
			chain[5] = (5 << 8) + 4;
{'fraction_non_alphanumeric': 0.18166194036263641, 'fraction_numerical': 0.03274039700953854, 'mean_word_length': 2.7325208466966004, 'pattern_counts': {'":': 0, '<': 109, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5249847', 'n_tokens_mistral': 5509, 'n_tokens_neox': 4679, 'n_words': 1360}