/* crypto/bn/bn_gf2m.c */
/* ====================================================================
* Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
*
* The Elliptic Curve Public-Key Crypto Library (ECC Code) included
* herein is developed by SUN MICROSYSTEMS, INC., and is contributed
* to the OpenSSL project.
*
* The ECC Code is licensed pursuant to the OpenSSL open source
* license provided below.
*
* In addition, Sun covenants to all licensees who provide a reciprocal
* covenant with respect to their own patents if any, not to sue under
* current and future patent claims necessarily infringed by the making,
* using, practicing, selling, offering for sale and/or otherwise
* disposing of the ECC Code as delivered hereunder (or portions thereof),
* provided that such covenant shall not apply:
* 1) for code that a licensee deletes from the ECC Code;
* 2) separates from the ECC Code; or
* 3) for infringements caused by:
* i) the modification of the ECC Code or
* ii) the combination of the ECC Code with other software or
* devices where such combination causes the infringement.
*
* The software is originally written by Sheueling Chang Shantz and
* Douglas Stebila of Sun Microsystems Laboratories.
*
*/
/*
* NOTE: This file is licensed pursuant to the OpenSSL license below and may
* be modified; but after modifications, the above covenant may no longer
* apply! In such cases, the corresponding paragraph ["In addition, Sun
* covenants ... causes the infringement."] and this note can be edited out;
* but please keep the Sun copyright notice and attribution.
*/
/* ====================================================================
* Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. All advertising materials mentioning features or use of this
* software must display the following acknowledgment:
* "This product includes software developed by the OpenSSL Project
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
*
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
* endorse or promote products derived from this software without
* prior written permission. For written permission, please contact
* openssl-core@openssl.org.
*
* 5. Products derived from this software may not be called "OpenSSL"
* nor may "OpenSSL" appear in their names without prior written
* permission of the OpenSSL Project.
*
* 6. Redistributions of any form whatsoever must retain the following
* acknowledgment:
* "This product includes software developed by the OpenSSL Project
* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
*
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
* ====================================================================
*
* This product includes cryptographic software written by Eric Young
* (eay@cryptsoft.com). This product includes software written by Tim
* Hudson (tjh@cryptsoft.com).
*
*/
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"
#ifndef OPENSSL_NO_EC2M
/*
* Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should
* fail.
*/
# define MAX_ITERATIONS 50
# define SQR_nibble(w) ((((w) & 8) << 3) \
| (((w) & 4) << 2) \
| (((w) & 2) << 1) \
| ((w) & 1))
/* Platform-specific macros to accelerate squaring. */
# if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
# define SQR1(w) \
SQR_nibble((w) >> 60) << 56 | SQR_nibble((w) >> 56) << 48 | \
SQR_nibble((w) >> 52) << 40 | SQR_nibble((w) >> 48) << 32 | \
SQR_nibble((w) >> 44) << 24 | SQR_nibble((w) >> 40) << 16 | \
SQR_nibble((w) >> 36) << 8 | SQR_nibble((w) >> 32)
# define SQR0(w) \
SQR_nibble((w) >> 28) << 56 | SQR_nibble((w) >> 24) << 48 | \
SQR_nibble((w) >> 20) << 40 | SQR_nibble((w) >> 16) << 32 | \
SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >> 8) << 16 | \
SQR_nibble((w) >> 4) << 8 | SQR_nibble((w) )
# endif
# ifdef THIRTY_TWO_BIT
# define SQR1(w) \
SQR_nibble((w) >> 28) << 24 | SQR_nibble((w) >> 24) << 16 | \
SQR_nibble((w) >> 20) << 8 | SQR_nibble((w) >> 16)
# define SQR0(w) \
SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >> 8) << 16 | \
SQR_nibble((w) >> 4) << 8 | SQR_nibble((w) )
# endif
# if !defined(OPENSSL_BN_ASM_GF2m)
/*
* Product of two polynomials a, b each with degree < BN_BITS2 - 1, result is
* a polynomial r with degree < 2 * BN_BITS - 1 The caller MUST ensure that
* the variables have the right amount of space allocated.
*/
# ifdef THIRTY_TWO_BIT
static void bn_GF2m_m