bn16.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* Copyright (c) 2001 by Sun Microsystems, Inc.
* All rights reserved.
*/
/*
* Cylink Corporation � 1998
*
* This software is licensed by Cylink to the Internet Software Consortium to
* promote implementation of royalty free public key cryptography within IETF
* standards. Cylink wishes to expressly thank the contributions of Dr.
* Martin Hellman, Whitfield Diffie, Ralph Merkle and Stanford University for
* their contributions to Internet Security. In accordance with the terms of
* this license, ISC is authorized to distribute and sublicense this software
* for the practice of IETF standards.
*
* The software includes BigNum, written by Colin Plumb and licensed by Philip
* R. Zimmermann for royalty free use and distribution with Cylink's
* software. Use of BigNum as a stand alone product or component is
* specifically prohibited.
*
* Disclaimer of All Warranties. THIS SOFTWARE IS BEING PROVIDED "AS IS",
* WITHOUT ANY EXPRESSED OR IMPLIED WARRANTY OF ANY KIND WHATSOEVER. IN
* PARTICULAR, WITHOUT LIMITATION ON THE GENERALITY OF THE FOREGOING, CYLINK
* MAKES NO REPRESENTATION OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
* PURPOSE.
*
* Cylink or its representatives shall not be liable for tort, indirect,
* special or consequential damages such as loss of profits or loss of
* goodwill from the use or inability to use the software for any purpose or
* for any reason whatsoever.
*
* EXPORT LAW: Export of the Foundations Suite may be subject to compliance
* with the rules and regulations promulgated from time to time by the Bureau
* of Export Administration, United States Department of Commerce, which
* restrict the export and re-export of certain products and technical data.
* If the export of the Foundations Suite is controlled under such rules and
* regulations, then the Foundations Suite shall not be exported or
* re-exported, directly or indirectly, (a) without all export or re-export
* licenses and governmental approvals required by any applicable laws, or (b)
* in violation of any applicable prohibition against the export or re-export
* of any part of the Foundations Suite. All export licenses for software
* containing the Foundations Suite are the sole responsibility of the licensee.
*/
/*
* bn16.c - the high-level bignum interface
*
* Like lbn16.c, this reserves the string "16" for textual replacement.
* The string must not appear anywhere unless it is intended to be replaced
* to generate other bignum interface functions.
*
* Copyright (c) 1995 Colin Plumb. All rights reserved.
* For licensing and other legal details, see the file legal.c.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#ifndef HAVE_CONFIG_H
#define HAVE_CONFIG_H 0
#endif
#if HAVE_CONFIG_H
#include "config.h"
#endif
/*
* Some compilers complain about #if FOO if FOO isn't defined,
* so do the ANSI-mandated thing explicitly...
*/
#ifndef NO_ASSERT_H
#define NO_ASSERT_H 0
#endif
#ifndef NO_STRING_H
#define NO_STRING_H 0
#endif
#ifndef HAVE_STRINGS_H
#define HAVE_STRINGS_H 0
#endif
#ifndef NEED_MEMORY_H
#define NEED_MEMORY_H 0
#endif
#if !NO_ASSERT_H
#include <assert.h>
#else
#define assert(x) (void)0
#endif
#if !NO_STRING_H
#include <string.h> /* for memmove() in bnMakeOdd */
#include <strings.h>
#endif
#if NEED_MEMORY_H
#include <memory.h>
#endif
/*
* This was useful during debugging, so it's left in here.
* You can ignore it. DBMALLOC is generally undefined.
*/
#ifndef DBMALLOC
#define DBAMLLOC 0
#endif
#if DBMALLOC
#else
#define MALLOCDB (void)0
#endif
#include "lbn.h"
#include "lbn16.h"
#include "lbnmem.h"
#include "bn16.h"
#include "bn.h"
/* Work-arounds for some particularly broken systems */
#include "kludge.h" /* For memmove() */
#include <port_after.h>
/* Functions */
void
bnInit_16(void)
{
}
void
{
}
}
/* Internal function. It operates in words. */
static int
{
void *p;
/* Round size up: most mallocs impose 8-byte granularity anyway */
if (!p)
return -1;
return 0;
}
return -1
int
{
return 0;
}
int
{
return 0;
}
void
{
}
/*
* Convert a bignum to big-endian bytes. Returns, in big-endian form, a
* substring of the bignum starting from lsbyte and "len" bytes long.
* Unused high-order (leading) bytes are filled with 0.
*/
void
{
/* Fill unused leading bytes with 0 */
*dest++ = 0;
len--;
}
if (len)
}
int
{
/* Pad with zeros as required */
if (s < words) {
s = words;
}
return 0;
}
/*
* Convert a bignum to little-endian bytes. Returns, in little-endian form, a
* substring of the bignum starting from lsbyte and "len" bytes long.
* Unused high-order (trailing) bytes are filled with 0.
*/
void
{
/* Fill unused leading bytes with 0 */
if (len)
}
int
{
/* Pad with zeros as required */
if (s < words) {
s = words;
}
return 0;
}
/* Return the least-significant word of the input. */
unsigned
{
}
unsigned
{
}
int
{
BNWORD16 t;
if (!s)
return 0;
bnSizeCheck(dest, s);
if (d < s) {
}
if (t) {
if (d > s) {
d-s, t);
}
if (t) {
}
}
return 0;
}
/*
* dest -= src.
* If dest goes negative, this produces the absolute value of
* the difference (the negative of the true value) and returns 1.
* Otherwise, it returls 0.
*/
int
{
BNWORD16 t;
bnSizeCheck(dest, s);
}
if (!s)
return 0;
if (t) {
if (d > s) {
d-s, t);
}
if (t) {
return 1;
}
}
return 0;
}
/*
* Compare the BigNum to the given value, which must be < 65536.
* Returns -1. 0 or 1 if a<b, a == b or a>b.
* a <=> b --> bnCmpQ(a,b) <=> 0
*/
int
{
unsigned t;
BNWORD16 v;
/* If a is more than one word long or zero, it's easy... */
if (t != 1)
return (t > 1) ? 1 : (b ? -1 : 0);
return (v > b) ? 1 : ((v < b) ? -1 : 0);
}
int
{
if (src) {
} else {
}
return 0;
}
int
{
BNWORD16 t;
if (t) {
}
return 0;
}
/*
* Return value as for bnSub: 1 if subtract underflowed, in which
* case the return is the negative of the computed value.
*/
int
{
BNWORD16 t;
if (t) {
/* Underflow. <= 1 word, so do it simply. */
return 1;
}
/* Try to normalize? Needing this is going to be very rare. */
/* dest->size = lbnNorm_16((BNWORD16 *)dest->ptr, dest->size); */
return 0;
}
/*
* Compare two BigNums. Returns -1. 0 or 1 if a<b, a == b or a>b.
* a <=> b --> bnCmp(a,b) <=> 0
*/
int
{
unsigned s, t;
if (s != t)
return s > t ? 1 : -1;
}
int
{
unsigned s;
if (!s) {
return 0;
}
if (!srcbuf)
return -1;
} else {
}
return 0;
}
int
{
unsigned s, t;
if (!s || !t) {
return 0;
}
if (a == b)
return bnSquare_16(dest, a);
bnSizeCheck(dest, s+t);
if (dest == a) {
if (!srcbuf)
return -1;
} else if (dest == b) {
if (!srcbuf)
return -1;
srcbuf, t);
} else {
}
return 0;
}
int
{
unsigned s;
if (!s || !b) {
return 0;
}
if (b == 1)
return 0;
}
int
struct BigNum const *d)
{
q->size = 0; /* No quotient */
return 0; /* Success */
}
if (r != n) { /* You are allowed to reduce in place */
bnSizeCheck(r, nsize);
}
if (qhigh) {
} else {
}
return 0;
}
int
{
}
return 0;
}
return 0;
}
unsigned
{
unsigned s;
if (!s)
return 0;
}
int
{
return -1; /* Illegal modulus! */
/* Special-case base of 2 */
return -1;
} else {
return -1;
}
return 0;
}
int
{
return -1; /* Illegal modulus! */
return -1;
return 0;
}
int
{
return -1; /* Illegal modulus! */
bnSizeCheck(n, msize);
return -1;
return 0;
}
int
{
int i;
/* Kind of silly, but we might as well permit it... */
if (a == b)
/* Ensure a is not the same as "dest" */
if (a == dest) {
a = b;
b = dest;
}
/* Copy a to tmp */
if (!tmp)
return -1;
/* Copy b to dest,if necessary */
if (dest != b)
{
if (i >= 0) {
} else {
(unsigned)-i);
}
} else {
if (i <= 0) {
} else {
(unsigned)i);
}
}
return 0;
}
int
{
unsigned s, m;
int i;
/* lbnInv_16 requires that the input be less than the modulus */
if (m < s ||
{
bnSizeCheck(dest, s + (m==s));
/* Pre-reduce modulo the modulus */
} else {
}
if (i == 0)
return i;
}
/*
* Shift a bignum left the appropriate number of bits,
* multiplying by 2^amt.
*/
int
{
if (amt % 16) {
if (carry) {
s++;
bnSizeCheck(dest, s);
}
}
amt /= 16;
if (amt) {
s * sizeof(BNWORD16));
s += amt;
}
return 0;
}
/*
* Shift a bignum right the appropriate number of bits,
* dividing by 2^amt.
*/
{
if (amt >= 16) {
s -= amt/16;
amt %= 16;
}
if (amt)
}
/*
* Shift a bignum right until it is odd, and return the number of
* bits shifted. n = d * 2^s. Replaces n with d and returns s.
* Returns 0 when given 0. (Another valid answer is infinity.)
*/
unsigned
bnMakeOdd_16(struct BigNum *n)
{
unsigned size;
unsigned s; /* shift amount */
BNWORD16 *p;
BNWORD16 t;
if (!size)
return 0;
t = BIGLITTLE(p[-1],p[0]);
s = 0;
/* See how many words we have to shift */
if (!t) {
/* Shift by words */
do {
s++;
BIGLITTLE(--p,p++);
} while ((t = BIGLITTLE(p[-1],p[0])) == 0);
size -= s;
s *= 16;
}
assert(t);
/* Now count the bits */
while ((t & 1) == 0) {
t >>= 1;
s++;
}
/* Shift the bits */
if (s & (16-1)) {
/* Renormalize */
--size;
}
return s;
}