bn_lib.c

RMI的处理器au1200系列所用的BOOTLOAD,包括SD卡启动USB启动硬盘启动网络启动,并初始化硬件的所有参数,支持内核调试.

/* crypto/bn/bn_lib.c */
/* Copyright (C) 1995-1998 Eric Young ([e-mail])
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young ([e-mail]).
 * The implementation was written so as to conform with Netscapes SSL.
 *
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson ([e-mail]).
 *
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 *
 * 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 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 acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young ([e-mail])"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson ([e-mail])"
 *
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS 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 AUTHOR OR 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.
 *
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

#ifndef BN_DEBUG
# undef NDEBUG			/* avoid conflicting definitions */
# define NDEBUG
#endif

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"
#include "workaround.h"

const char *BN_version = "Big Number" OPENSSL_VERSION_PTEXT;

/* For a 32 bit machine
 * 2 -   4 ==  128
 * 3 -   8 ==  256
 * 4 -  16 ==  512
 * 5 -  32 == 1024
 * 6 -  64 == 2048
 * 7 - 128 == 4096
 * 8 - 256 == 8192
 */
static int bn_limit_bits = 0;
static int bn_limit_num = 8;	/* (1<<bn_limit_bits) */
static int bn_limit_bits_low = 0;
static int bn_limit_num_low = 8;	/* (1<<bn_limit_bits_low) */
static int bn_limit_bits_high = 0;
static int bn_limit_num_high = 8;	/* (1<<bn_limit_bits_high) */
static int bn_limit_bits_mont = 0;
static int bn_limit_num_mont = 8;	/* (1<<bn_limit_bits_mont) */

void BN_set_params(int mult, int high, int low, int mont)
{
    if (mult >= 0) {
	if (mult > (sizeof(int) * 8) - 1)
	    mult = sizeof(int) * 8 - 1;
	bn_limit_bits = mult;
	bn_limit_num = 1 << mult;
    }
    if (high >= 0) {
	if (high > (sizeof(int) * 8) - 1)
	    high = sizeof(int) * 8 - 1;
	bn_limit_bits_high = high;
	bn_limit_num_high = 1 << high;
    }
    if (low >= 0) {
	if (low > (sizeof(int) * 8) - 1)
	    low = sizeof(int) * 8 - 1;
	bn_limit_bits_low = low;
	bn_limit_num_low = 1 << low;
    }
    if (mont >= 0) {
	if (mont > (sizeof(int) * 8) - 1)
	    mont = sizeof(int) * 8 - 1;
	bn_limit_bits_mont = mont;
	bn_limit_num_mont = 1 << mont;
    }
}

int BN_get_params(int which)
{
    if (which == 0)
	return (bn_limit_bits);
    else if (which == 1)
	return (bn_limit_bits_high);
    else if (which == 2)
	return (bn_limit_bits_low);
    else if (which == 3)
	return (bn_limit_bits_mont);
    else
	return (0);
}

BIGNUM *BN_value_one(void)
{
    static BN_ULONG data_one = 1L;
    static BIGNUM const_one = { &data_one, 1, 1, 0 };

    return (&const_one);
}

char *BN_options(void)
{
    static int init = 0;
    static char data[16];

    if (!init) {
	init++;
#ifndef ROM_BASED
#ifdef BN_LLONG
	sprintf(data, "bn(%d,%d)", (int) sizeof(BN_ULLONG) * 8,
		(int) sizeof(BN_ULONG) * 8);
#else
	sprintf(data, "bn(%d,%d)", (int) sizeof(BN_ULONG) * 8,
		(int) sizeof(BN_ULONG) * 8);
#endif
#endif				//SECUREBOOT
    }
    return (data);
}

int BN_num_bits_word(BN_ULONG l)
{
    static const char bits[256] = {
	0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
	8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    };

#if defined(SIXTY_FOUR_BIT_LONG)
    if (l & 0xffffffff00000000L) {
	if (l & 0xffff000000000000L) {
	    if (l & 0xff00000000000000L) {
		return (bits[(int) (l >> 56)] + 56);
	    } else
		return (bits[(int) (l >> 48)] + 48);
	} else {
	    if (l & 0x0000ff0000000000L) {
		return (bits[(int) (l >> 40)] + 40);
	    } else
		return (bits[(int) (l >> 32)] + 32);
	}
    } else
#else
#ifdef SIXTY_FOUR_BIT
    if (l & 0xffffffff00000000LL) {
	if (l & 0xffff000000000000LL) {
	    if (l & 0xff00000000000000LL) {
		return (bits[(int) (l >> 56)] + 56);
	    } else
		return (bits[(int) (l >> 48)] + 48);
	} else {
	    if (l & 0x0000ff0000000000LL) {
		return (bits[(int) (l >> 40)] + 40);
	    } else
		return (bits[(int) (l >> 32)] + 32);
	}
    } else
#endif
#endif
    {
#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
	if (l & 0xffff0000L) {
	    if (l & 0xff000000L)
		return (bits[(int) (l >> 24L)] + 24);
	    else
		return (bits[(int) (l >> 16L)] + 16);
	} else
#endif
	{
#if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
	    if (l & 0xff00L)
		return (bits[(int) (l >> 8)] + 8);
	    else
#endif
		return (bits[(int) (l)]);
	}
    }
}

int BN_num_bits(const BIGNUM * a)
{
    BN_ULONG l;
    int i;

    bn_check_top(a);

    if (a->top == 0)
	return (0);
    l = a->d[a->top - 1];
    assert(l != 0);
    i = (a->top - 1) * BN_BITS2;
    return (i + BN_num_bits_word(l));
}

void BN_clear_free(BIGNUM * a)
{
    int i;

    if (a == NULL)
	return;
    if (a->d != NULL) {
	memset(a->d, 0, a->dmax * sizeof(a->d[0]));
	if (!(BN_get_flags(a, BN_FLG_STATIC_DATA)))
	    OPENSSL_free(a->d);
    }
    i = BN_get_flags(a, BN_FLG_MALLOCED);
    memset(a, 0, sizeof(BIGNUM));
    if (i)
	OPENSSL_free(a);
}

void BN_free(BIGNUM * a)
{
    if (a == NULL)
	return;
    if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA)))
	OPENSSL_free(a->d);
    a->flags |= BN_FLG_FREE;	/* REMOVE? */
    if (a->flags & BN_FLG_MALLOCED)
	OPENSSL_free(a);
}

void BN_init(BIGNUM * a)
{
    memset(a, 0, sizeof(BIGNUM));
}

BIGNUM *BN_new(void)
{
    BIGNUM *ret;

    if ((ret = (BIGNUM *) Our_malloc(sizeof(BIGNUM))) == NULL) {
	BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
	return (NULL);
    }
    ret->flags = BN_FLG_MALLOCED;
    ret->top = 0;
    ret->neg = 0;
    ret->dmax = 0;
    ret->d = NULL;
    return (ret);
}

/* This is an internal function that should not be used in applications.
 * It ensures that 'b' has enough room for a 'words' word number number.
 * It is mostly used by the various BIGNUM routines. If there is an error,
 * NULL is returned. If not, 'b' is returned. */

BIGNUM *bn_expand2(BIGNUM * b, int words)
{
    BN_ULONG *A, *a;
    const BN_ULONG *B;
    int i;

    bn_check_top(b);

    if (words > b->dmax) {
	if (words > (INT_MAX / (4 * BN_BITS2))) {
	    BNerr(BN_F_BN_EXPAND2, BN_R_BIGNUM_TOO_LONG);
	    return NULL;
	}

	bn_check_top(b);
	if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
	    BNerr(BN_F_BN_EXPAND2, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
	    return (NULL);
	}
	a = A = (BN_ULONG *) Our_malloc(sizeof(BN_ULONG) * (words + 1));
	if (A == NULL) {
	    BNerr(BN_F_BN_EXPAND2, ERR_R_MALLOC_FAILURE);
	    return (NULL);
	}
#if 1
	B = b->d;
	/* Check if the previous number needs to be copied */
	if (B != NULL) {
#if 0
	    /* This lot is an unrolled loop to copy b->top
	     * BN_ULONGs from B to A
	     */
/*
 * I have nothing against unrolling but it's usually done for
 * several reasons, namely:
 * - minimize percentage of decision making code, i.e. branches;
 * - avoid cache trashing;
 * - make it possible to schedule loads earlier;
 * Now let's examine the code below. The cornerstone of C is
 * "programmer is always right" and that's what we love it for:-)
 * For this very reason C compilers have to be paranoid when it
 * comes to data aliasing and assume the worst. Yeah, but what
 * does it mean in real life? This means that loop body below will
 * be compiled to sequence of loads immediately followed by stores
 * as compiler assumes the worst, something in A==B+1 style. As a
 * result CPU pipeline is going to starve for incoming data. Secondly
 * if A and B happen to share same cache line such code is going to
 * cause severe cache trashing. Both factors have severe impact on
 * performance of modern CPUs and this is the reason why this
 * particular piece of code is #ifdefed away and replaced by more
 * "friendly" version found in #else section below. This comment
 * also applies to BN_copy function.
 *
 *					<[e-mail]>
 */
	    for (i = b->top & (~7); i > 0; i -= 8) {
		A[0] = B[0];
		A[1] = B[1];
		A[2] = B[2];
		A[3] = B[3];
		A[4] = B[4];
		A[5] = B[5];
		A[6] = B[6];
		A[7] = B[7];
		A += 8;
		B += 8;
	    }
	    switch (b->top & 7) {
	    case 7:
		A[6] = B[6];
	    case 6:
		A[5] = B[5];
	    case 5:
		A[4] = B[4];
	    case 4:
		A[3] = B[3];
	    case 3:
		A[2] = B[2];
	    case 2:
		A[1] = B[1];
	    case 1:
		A[0] = B[0];
	    case 0:
		/* I need the 'case 0' entry for utrix cc.
		 * If the optimizer is turned on, it does the
		 * switch table by doing
		 * a=top&7
		 * a--;
		 * goto jump_table[a];
		 * If top is 0, this makes us jump to 0xffffffc