<commit_before>/* Copyright (c) 2015 Cryptography Research, Inc.
 * Released under the MIT License.  See LICENSE.txt for license information.
 */

/**
 * @file decaf.c
 * @author <NAME>
 * @brief Decaf high-level functions.
 */

#define __STDC_WANT_LIB_EXT1__ 1 /* for memset_s */
#include "decaf.h"
#include <string.h>
#include "field.h"

#include "ec_point.h" // REMOVE!

#define WBITS DECAF_WORD_BITS

#if WBITS == 64
#define LBITS 56
typedef __uint128_t decaf_dword_t;
typedef __int128_t decaf_sdword_t;
#define LIMB(x) (x##ull)
#define SC_LIMB(x) (x##ull)
#elif WBITS == 32
typedef uint64_t decaf_dword_t;
typedef int64_t decaf_sdword_t;
#define LBITS 28
#define LIMB(x) (x##ull)&((1ull<<LBITS)-1), (x##ull)>>LBITS
#define SC_LIMB(x) (x##ull)&((1ull<<32)-1), (x##ull)>>32
#else
#error "Only supporting 32- and 64-bit platforms right now"
#endif

static const int QUADRATIC_NONRESIDUE = -1;

#define sv static void
typedef decaf_word_t gf[DECAF_448_LIMBS] __attribute__((aligned(32)));
static const gf ZERO = {0}, ONE = {1}, TWO = {2};

#define LMASK ((((decaf_word_t)1)<<LBITS)-1)
#if WBITS == 64
static const gf P = { LMASK, LMASK, LMASK, LMASK, LMASK-1, LMASK, LMASK, LMASK };
#else
static const gf P = { LMASK,   LMASK, LMASK, LMASK, LMASK, LMASK, LMASK, LMASK,
		      LMASK-1, LMASK, LMASK, LMASK, LMASK, LMASK, LMASK, LMASK };
#endif
static const int EDWARDS_D = -39081;

const decaf_448_scalar_t decaf_448_scalar_p = {{{
    SC_LIMB(0x2378c292ab5844f3),
    SC_LIMB(0x216cc2728dc58f55),
    SC_LIMB(0xc44edb49aed63690),
    SC_LIMB(0xffffffff7cca23e9),
    SC_LIMB(0xffffffffffffffff),
    SC_LIMB(0xffffffffffffffff),
    SC_LIMB(0x3fffffffffffffff)
}}}, decaf_448_scalar_one = {{{1}}}, decaf_448_scalar_zero = {{{0}}};

static const decaf_448_scalar_t decaf_448_scalar_r2 = {{{
    SC_LIMB(0xe3539257049b9b60),
    SC_LIMB(0x7af32c4bc1b195d9),
    SC_LIMB(0x0d66de2388ea1859),
    SC_LIMB(0xae17cf725ee4d838),
    SC_LIMB(0x1a9cc14ba3c47c44),
    SC_LIMB(0x2052bcb7e4d070af),
    SC_LIMB(0x3402a939f823b729)
}}};

static const decaf_word_t DECAF_MONTGOMERY_FACTOR = (decaf_word_t)(0x3bd440fae918bc5ull);

/** base = twist of Goldilocks base point (~,19). */

const decaf_448_point_t decaf_448_point_base = {{
    { LIMB(0xb39a2d57e08c7b),LIMB(0xb38639c75ff281),
      LIMB(0x2ec981082b3288),LIMB(0x99fe8607e5237c),
      LIMB(0x0e33fbb1fadd1f),LIMB(0xe714f67055eb4a),
      LIMB(0xc9ae06d64067dd),LIMB(0xf7be45054760fa) },
    { LIMB(0xbd8715f551617f),LIMB(0x8c17fbeca8f5fc),
      LIMB(0xaae0eec209c06f),LIMB(0xce41ad80cbe6b8),
      LIMB(0xdf360b5c828c00),LIMB(0xaf25b6bbb40e3b),
      LIMB(0x8ed37f0ce4ed31),LIMB(0x72a1c3214557b9) },
    { 1 },
    { LIMB(0x97ca9c8ed8bde9),LIMB(0xf0b780da83304c),
      LIMB(0x0d79c0a7729a69),LIMB(0xc18d3f24aebc1c),
      LIMB(0x1fbb5389b3fda5),LIMB(0xbb24f674635948),
      LIMB(0x723a55709a3983),LIMB(0xe1c0107a823dd4) }
}};

struct decaf_448_precomputed_s {
    decaf_448_point_t p[1];
};

const struct decaf_448_precomputed_s *decaf_448_precomputed_base =
    (const struct decaf_448_precomputed_s *)decaf_448_point_base;

const size_t sizeof_decaf_448_precomputed_s = sizeof(struct decaf_448_precomputed_s);
const size_t alignof_decaf_448_precomputed_s = 32;

#if (defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__)) || defined(DECAF_FORCE_UNROLL)
    #if DECAF_448_LIMBS==8
    #define FOR_LIMB(i,op) { unsigned int i=0; \
       op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; \
    }
    #elif DECAF_448_LIMBS==16
    #define FOR_LIMB(i,op) { unsigned int i=0; \
       op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; \
       op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; \
    }
    #else
    #define FOR_LIMB(i,op) { unsigned int i=0; for (i=0; i<DECAF_448_LIMBS; i++)  { op; }}
    #endif
#else
#define FOR_LIMB(i,op) { unsigned int i=0; for (i=0; i<DECAF_448_LIMBS; i++)  { op; }}
#endif

/** Copy x = y */
sv gf_cpy(gf x, const gf y) { FOR_LIMB(i, x[i] = y[i]); }

/** Mostly-unoptimized multiply (PERF), but at least it's unrolled. */
static inline void gf_mul (gf c, const gf a, const gf b) {
    field_mul((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** No dedicated square (PERF) */
static inline void gf_sqr (gf c, const gf a) {
    field_sqr((field_t *)c, (const field_t *)a);
}

/** Inverse square root using addition chain. */
sv gf_isqrt(gf y, const gf x) {
    field_isr((field_t *)y, (const field_t *)x);
}

/** Add mod p.  Conservatively always weak-reduce. (PERF) */
static inline void gf_add ( gf c, const gf a, const gf b ) {
    field_add((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** Subtract mod p.  Conservatively always weak-reduce. (PERF) */
static inline void gf_sub ( gf c, const gf a, const gf b ) {
    field_sub((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** Add mod p.  Conservatively always weak-reduce. (PERF) */
static inline void gf_bias ( gf c, int amt) {
    field_bias((field_t *)c, amt);
}

/** Subtract mod p.  Bias by 2 and don't reduce  */
static inline void gf_sub_nr ( gf c, const gf a, const gf b ) {
    ANALYZE_THIS_ROUTINE_CAREFULLY; //TODO
    field_sub_nr((field_t *)c, (const field_t *)a, (const field_t *)b);
    gf_bias(c, 2);
}

/** Subtract mod p. Bias by amt but don't reduce.  */
static inline void gf_sub_nr_x ( gf c, const gf a, const gf b, int amt ) {
    ANALYZE_THIS_ROUTINE_CAREFULLY; //TODO
    field_sub_nr((field_t *)c, (const field_t *)a, (const field_t *)b);
    gf_bias(c, amt);
}

/** Add mod p.  Don't reduce. */
static inline void gf_add_nr ( gf c, const gf a, const gf b ) {
    ANALYZE_THIS_ROUTINE_CAREFULLY; //TODO
    field_add_nr((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** Constant time, x = is_z ? z : y */
sv cond_sel(gf x, const gf y, const gf z, decaf_bool_t is_z) {
    FOR_LIMB(i, x[i] = (y[i] & ~is_z) | (z[i] & is_z) );
}

/** Constant time, if (neg) x=-x; */
sv cond_neg(gf x, decaf_bool_t neg) {
    gf y;
    gf_sub(y,ZERO,x);
    cond_sel(x,x,y,neg);
}

/** Constant time, if (swap) (x,y) = (y,x); */
sv cond_swap(gf x, gf y, decaf_bool_t swap) {
    FOR_LIMB(i, {
        decaf_word_t s = (x[i] ^ y[i]) & swap;
        x[i] ^= s;
        y[i] ^= s;
    });
}
<commit_msg>condswap is the main remaining bottleneck on monty ladder.  comment in a pragma but dont actually use it yet...<commit_after>/* Copyright (c) 2015 Cryptography Research, Inc.
 * Released under the MIT License.  See LICENSE.txt for license information.
 */

/**
 * @file decaf.c
 * @author <NAME>
 * @brief Decaf high-level functions.
 */

#define __STDC_WANT_LIB_EXT1__ 1 /* for memset_s */
#include "decaf.h"
#include <string.h>
#include "field.h"

#include "ec_point.h" // REMOVE!

#define WBITS DECAF_WORD_BITS

#if WBITS == 64
#define LBITS 56
typedef __uint128_t decaf_dword_t;
typedef __int128_t decaf_sdword_t;
#define LIMB(x) (x##ull)
#define SC_LIMB(x) (x##ull)
#elif WBITS == 32
typedef uint64_t decaf_dword_t;
typedef int64_t decaf_sdword_t;
#define LBITS 28
#define LIMB(x) (x##ull)&((1ull<<LBITS)-1), (x##ull)>>LBITS
#define SC_LIMB(x) (x##ull)&((1ull<<32)-1), (x##ull)>>32
#else
#error "Only supporting 32- and 64-bit platforms right now"
#endif

static const int QUADRATIC_NONRESIDUE = -1;

#define sv static void
typedef decaf_word_t gf[DECAF_448_LIMBS] __attribute__((aligned(32)));
static const gf ZERO = {0}, ONE = {1}, TWO = {2};

#define LMASK ((((decaf_word_t)1)<<LBITS)-1)
#if WBITS == 64
static const gf P = { LMASK, LMASK, LMASK, LMASK, LMASK-1, LMASK, LMASK, LMASK };
#else
static const gf P = { LMASK,   LMASK, LMASK, LMASK, LMASK, LMASK, LMASK, LMASK,
		      LMASK-1, LMASK, LMASK, LMASK, LMASK, LMASK, LMASK, LMASK };
#endif
static const int EDWARDS_D = -39081;

const decaf_448_scalar_t decaf_448_scalar_p = {{{
    SC_LIMB(0x2378c292ab5844f3),
    SC_LIMB(0x216cc2728dc58f55),
    SC_LIMB(0xc44edb49aed63690),
    SC_LIMB(0xffffffff7cca23e9),
    SC_LIMB(0xffffffffffffffff),
    SC_LIMB(0xffffffffffffffff),
    SC_LIMB(0x3fffffffffffffff)
}}}, decaf_448_scalar_one = {{{1}}}, decaf_448_scalar_zero = {{{0}}};

static const decaf_448_scalar_t decaf_448_scalar_r2 = {{{
    SC_LIMB(0xe3539257049b9b60),
    SC_LIMB(0x7af32c4bc1b195d9),
    SC_LIMB(0x0d66de2388ea1859),
    SC_LIMB(0xae17cf725ee4d838),
    SC_LIMB(0x1a9cc14ba3c47c44),
    SC_LIMB(0x2052bcb7e4d070af),
    SC_LIMB(0x3402a939f823b729)
}}};

static const decaf_word_t DECAF_MONTGOMERY_FACTOR = (decaf_word_t)(0x3bd440fae918bc5ull);

/** base = twist of Goldilocks base point (~,19). */

const decaf_448_point_t decaf_448_point_base = {{
    { LIMB(0xb39a2d57e08c7b),LIMB(0xb38639c75ff281),
      LIMB(0x2ec981082b3288),LIMB(0x99fe8607e5237c),
      LIMB(0x0e33fbb1fadd1f),LIMB(0xe714f67055eb4a),
      LIMB(0xc9ae06d64067dd),LIMB(0xf7be45054760fa) },
    { LIMB(0xbd8715f551617f),LIMB(0x8c17fbeca8f5fc),
      LIMB(0xaae0eec209c06f),LIMB(0xce41ad80cbe6b8),
      LIMB(0xdf360b5c828c00),LIMB(0xaf25b6bbb40e3b),
      LIMB(0x8ed37f0ce4ed31),LIMB(0x72a1c3214557b9) },
    { 1 },
    { LIMB(0x97ca9c8ed8bde9),LIMB(0xf0b780da83304c),
      LIMB(0x0d79c0a7729a69),LIMB(0xc18d3f24aebc1c),
      LIMB(0x1fbb5389b3fda5),LIMB(0xbb24f674635948),
      LIMB(0x723a55709a3983),LIMB(0xe1c0107a823dd4) }
}};

struct decaf_448_precomputed_s {
    decaf_448_point_t p[1];
};

const struct decaf_448_precomputed_s *decaf_448_precomputed_base =
    (const struct decaf_448_precomputed_s *)decaf_448_point_base;

const size_t sizeof_decaf_448_precomputed_s = sizeof(struct decaf_448_precomputed_s);
const size_t alignof_decaf_448_precomputed_s = 32;

#if (defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__)) || defined(DECAF_FORCE_UNROLL)
    #if DECAF_448_LIMBS==8
    #define FOR_LIMB(i,op) { unsigned int i=0; \
       op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; \
    }
    #elif DECAF_448_LIMBS==16
    #define FOR_LIMB(i,op) { unsigned int i=0; \
       op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; \
       op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; op;i++; \
    }
    #else
    #define FOR_LIMB(i,op) { unsigned int i=0; for (i=0; i<DECAF_448_LIMBS; i++)  { op; }}
    #endif
#else
#define FOR_LIMB(i,op) { unsigned int i=0; for (i=0; i<DECAF_448_LIMBS; i++)  { op; }}
#endif

/** Copy x = y */
sv gf_cpy(gf x, const gf y) { FOR_LIMB(i, x[i] = y[i]); }

/** Mostly-unoptimized multiply (PERF), but at least it's unrolled. */
static inline void gf_mul (gf c, const gf a, const gf b) {
    field_mul((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** No dedicated square (PERF) */
static inline void gf_sqr (gf c, const gf a) {
    field_sqr((field_t *)c, (const field_t *)a);
}

/** Inverse square root using addition chain. */
sv gf_isqrt(gf y, const gf x) {
    field_isr((field_t *)y, (const field_t *)x);
}

/** Add mod p.  Conservatively always weak-reduce. (PERF) */
static inline void gf_add ( gf c, const gf a, const gf b ) {
    field_add((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** Subtract mod p.  Conservatively always weak-reduce. (PERF) */
static inline void gf_sub ( gf c, const gf a, const gf b ) {
    field_sub((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** Add mod p.  Conservatively always weak-reduce. (PERF) */
static inline void gf_bias ( gf c, int amt) {
    field_bias((field_t *)c, amt);
}

/** Subtract mod p.  Bias by 2 and don't reduce  */
static inline void gf_sub_nr ( gf c, const gf a, const gf b ) {
    ANALYZE_THIS_ROUTINE_CAREFULLY; //TODO
    field_sub_nr((field_t *)c, (const field_t *)a, (const field_t *)b);
    gf_bias(c, 2);
}

/** Subtract mod p. Bias by amt but don't reduce.  */
static inline void gf_sub_nr_x ( gf c, const gf a, const gf b, int amt ) {
    ANALYZE_THIS_ROUTINE_CAREFULLY; //TODO
    field_sub_nr((field_t *)c, (const field_t *)a, (const field_t *)b);
    gf_bias(c, amt);
}

/** Add mod p.  Don't reduce. */
static inline void gf_add_nr ( gf c, const gf a, const gf b ) {
    ANALYZE_THIS_ROUTINE_CAREFULLY; //TODO
    field_add_nr((field_t *)c, (const field_t *)a, (const field_t *)b);
}

/** Constant time, x = is_z ? z : y */
sv cond_sel(gf x, const gf y, const gf z, decaf_bool_t is_z) {
    FOR_LIMB(i, x[i] = (y[i] & ~is_z) | (z[i] & is_z) );
}

/** Constant time, if (neg) x=-x; */
sv cond_neg(gf x, decaf_bool_t neg) {
    gf y;
    gf_sub(y,ZERO,x);
    cond_sel(x,x,y,neg);
}

/** Constant time, if (swap) (x,y) = (y,x); */
static inline void cond_swap(gf x, gf y, decaf_bool_t swap) {
    int i;
    /* PERF */
    //_Pragma("clang loop unroll(disable) vectorize(enable) vectorize_width(4) interleave_count(2)")
    for (i=0; i<DECAF_448_LIMBS; i++) {
        decaf_word_t s = (x[i] ^ y[i]) & swap;
        x[i] ^= s;
        y[i] ^= s;
    }
}

{'fraction_non_alphanumeric': 0.15438348638254454, 'fraction_numerical': 0.0783298014284593, 'mean_word_length': 4.243621399176955, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 8, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5169614', 'n_tokens_mistral': 6345, 'n_tokens_neox': 5693, 'n_words': 1232}