tinc(8): add history section

[plan9front.git] / sys / man / 2 / mp

diff --git a/sys/man/2/mp b/sys/man/2/mp
old mode 100755 (executable)
new mode 100644 (file)
index 9db58d1..4f54878
--- a/sys/man/2/mp
+++ b/sys/man/2/mp
@@ -1,6 +1,6 @@
 .TH MP 2
 .SH NAME
 .TH MP 2
 .SH NAME

-mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, strtomp, mpfmt,mptoa, betomp, mptobe, letomp, mptole, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpdiv, mpcmp, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic
+mpsetminbits, mpnew, mpfree, mpbits, mpnorm, mpcopy, mpassign, mprand, mpnrand, strtomp, mpfmt, mptoa, betomp, mptobe, mptober, letomp, mptole, mptolel, mptoui, uitomp, mptoi, itomp, uvtomp, mptouv, vtomp, mptov, mptod, dtomp, mpdigdiv, mpadd, mpsub, mpleft, mpright, mpmul, mpexp, mpmod, mpmodadd, mpmodsub, mpmodmul, mpdiv, mpcmp, mpsel, mpfactorial, mpextendedgcd, mpinvert, mpsignif, mplowbits0, mpvecdigmuladd, mpvecdigmulsub, mpvecadd, mpvecsub, mpveccmp, mpvecmul, mpmagcmp, mpmagadd, mpmagsub, crtpre, crtin, crtout, crtprefree, crtresfree \- extended precision arithmetic

 .SH SYNOPSIS
 .B #include <u.h>
 .br
 .SH SYNOPSIS
 .B #include <u.h>
 .br


@@ -22,7 +22,7 @@ void  mpsetminbits(int n)
 void   mpbits(mpint *b, int n)
 .PP
 .B
 void   mpbits(mpint *b, int n)
 .PP
 .B

-void   mpnorm(mpint *b)
+mpint* mpnorm(mpint *b)

 .PP
 .B
 mpint* mpcopy(mpint *b)
 .PP
 .B
 mpint* mpcopy(mpint *b)


@@ -34,6 +34,9 @@ void  mpassign(mpint *old, mpint *new)
 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
 .PP
 .B
 mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b)
 .PP
 .B

+mpint* mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b)
+.PP
+.B

 mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
 .PP
 .B
 mpint* strtomp(char *buf, char **rptr, int base, mpint *b)
 .PP
 .B


@@ -49,12 +52,18 @@ mpint*      betomp(uchar *buf, uint blen, mpint *b)
 int    mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
 .PP
 .B
 int    mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
 .PP
 .B

+void   mptober(mpint *b, uchar *buf, int blen)
+.PP
+.B

 mpint* letomp(uchar *buf, uint blen, mpint *b)
 .PP
 .B
 int    mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
 .PP
 .B
 mpint* letomp(uchar *buf, uint blen, mpint *b)
 .PP
 .B
 int    mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
 .PP
 .B

+void   mptolel(mpint *b, uchar *buf, int blen)
+.PP
+.B

 uint   mptoui(mpint*)
 .PP
 .B
 uint   mptoui(mpint*)
 .PP
 .B


@@ -79,6 +88,12 @@ mpint*       uvtomp(uvlong, mpint*)
 uvlong mptouv(mpint*)
 .PP
 .B
 uvlong mptouv(mpint*)
 .PP
 .B

+mpint* dtomp(double, mpint*)
+.PP
+.B
+double mptod(mpint*)
+.PP
+.B

 void   mpadd(mpint *b1, mpint *b2, mpint *sum)
 .PP
 .B
 void   mpadd(mpint *b1, mpint *b2, mpint *sum)
 .PP
 .B


@@ -97,6 +112,30 @@ void        mpleft(mpint *b, int shift, mpint *res)
 void   mpright(mpint *b, int shift, mpint *res)
 .PP
 .B
 void   mpright(mpint *b, int shift, mpint *res)
 .PP
 .B

+void   mpand(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void   mpbic(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void   mpor(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void   mpnot(mpint *b, mpint *res)
+.PP
+.B
+void   mpxor(mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+void   mptrunc(mpint *b, int n, mpint *res)
+.PP
+.B
+void   mpxtend(mpint *b, int n, mpint *res)
+.PP
+.B
+void   mpasr(mpint *b, int n, mpint *res)
+.PP
+.B

 void   mpmul(mpint *b1, mpint *b2, mpint *prod)
 .PP
 .B
 void   mpmul(mpint *b1, mpint *b2, mpint *prod)
 .PP
 .B


@@ -112,12 +151,27 @@ void      mpdiv(mpint *dividend, mpint *divisor,  mpint *quotient,
        mpint *remainder)
 .PP
 .B
        mpint *remainder)
 .PP
 .B

+void   mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
+.PP
+.B
+void   mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
+.PP
+.B
+void   mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
+.PP
+.B

 int    mpcmp(mpint *b1, mpint *b2)
 .PP
 .B
 int    mpmagcmp(mpint *b1, mpint *b2)
 .PP
 .B
 int    mpcmp(mpint *b1, mpint *b2)
 .PP
 .B
 int    mpmagcmp(mpint *b1, mpint *b2)
 .PP
 .B

+void   mpsel(int s, mpint *b1, mpint *b2, mpint *res)
+.PP
+.B
+mpint* mpfactorial(ulong n)
+.PP
+.B

 void   mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
 .br
 .B
 void   mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,
 .br
 .B


@@ -226,8 +280,9 @@ This includes
 .IR strtomp ,
 .IR itomp ,
 .IR uitomp ,
 .IR strtomp ,
 .IR itomp ,
 .IR uitomp ,

+.IR btomp ,

 and
 and

-.IR btomp .
+.IR dtomp .

 These functions, in addition to
 .I mpnew
 and
 These functions, in addition to
 .I mpnew
 and


@@ -300,6 +355,14 @@ bit random number using the generator
 takes a pointer to a string of uchar's and the number
 to fill in.
 .PP
 takes a pointer to a string of uchar's and the number
 to fill in.
 .PP

+.I Mpnrand
+uses
+.I gen
+to generate a uniform random number
+.IR x ,
+.if t 0 ≤ \fIx\fR < \fIn\fR.
+.if n 0 ≤ x < n.
+.PP

 .I Strtomp
 and
 .I mptoa
 .I Strtomp
 and
 .I mptoa


@@ -308,35 +371,51 @@ convert between
 and
 .B mpint
 representations using the base indicated.
 and
 .B mpint
 representations using the base indicated.

-Only the bases 10, 16, 32, and 64 are
-supported.  Anything else defaults to 16.
+Only the bases 2, 4, 8, 10, 16, 32, and 64 are
+supported.

 .IR Strtomp
 skips any leading spaces or tabs.
 .IR Strtomp 's
 scan stops when encountering a digit not valid in the
 base.  If
 .IR Strtomp
 skips any leading spaces or tabs.
 .IR Strtomp 's
 scan stops when encountering a digit not valid in the
 base.  If

+.I base
+is zero then C-style prefixes are interpreted to
+find the base:
+.B 0x
+for hexadecimal,
+.B 0b
+for binary and
+.B 0
+for octal. Otherwise decimal is assumed.

 .I rptr
 is not zero,
 .I *rptr
 is set to point to the character immediately after the
 string converted.
 .I rptr
 is not zero,
 .I *rptr
 is set to point to the character immediately after the
 string converted.

-If the parse pterminates before any digits are found,
+If the parse terminates before any digits are found,

 .I strtomp
 return
 .BR nil .
 .I Mptoa
 .I strtomp
 return
 .BR nil .
 .I Mptoa

-returns a pointer to the filled buffer.
+returns a pointer to the
+.SM ASCII
+filled buffer.

 If the parameter
 .I buf
 is
 .BR nil ,
 the buffer is allocated.
 If the parameter
 .I buf
 is
 .BR nil ,
 the buffer is allocated.

+Setting
+.I base
+to zero uses hexadecimal default.

 .I Mpfmt
 can be used with
 .IR fmtinstall (2)
 and
 .IR print (2)
 .I Mpfmt
 can be used with
 .IR fmtinstall (2)
 and
 .IR print (2)

-to print hexadecimal representations of
+to print
+.SM ASCII
+representations of

 .BR mpint s.
 The conventional verb is
 .LR B ,
 .BR mpint s.
 The conventional verb is
 .LR B ,


@@ -344,6 +423,8 @@ for which
 .I mp.h
 provides a
 .LR pragma .
 .I mp.h
 provides a
 .LR pragma .

+The precision in the format string changes the base,
+defaulting to hexadecimal when omited.

 .PP
 .I Mptobe
 and
 .PP
 .I Mptobe
 and


@@ -372,6 +453,24 @@ deposited in the location pointed to by
 Sign is ignored in these conversions, i.e., the byte
 array version is always positive.
 .PP
 Sign is ignored in these conversions, i.e., the byte
 array version is always positive.
 .PP

+.I Mptober
+and
+.I mptolel
+fill
+.I blen
+lower bytes of an
+.I mpint
+into a fixed length byte array.
+.I Mptober
+fills the bytes right adjusted in big endian order so that the least
+significant byte is at
+.I buf[blen-1]
+while
+.I mptolel
+fills in little endian order; left adjusted; so that the least
+significat byte is filled into
+.IR buf[0] .
+.PP

 .IR Betomp ,
 and
 .I letomp
 .IR Betomp ,
 and
 .I letomp


@@ -394,7 +493,7 @@ is
 .BR nil ,
 a new integer is allocated and returned as the result.
 .PP
 .BR nil ,
 a new integer is allocated and returned as the result.
 .PP

-The integer conversions are:
+The integer (and floating point) conversions are:

 .TF Mptouv
 .TP
 .I mptoui
 .TF Mptouv
 .TP
 .I mptoui


@@ -420,14 +519,25 @@ The integer conversions are:
 .TP
 .I vtomp
 .BR "vlong" -> mpint
 .TP
 .I vtomp
 .BR "vlong" -> mpint

+.TP
+.I mptod
+.BR mpint -> "double"
+.TP
+.I dtomp
+.BR "double" -> mpint

 .PD
 .PP
 When converting to the base integer types, if the integer is too large,
 the largest integer of the appropriate sign
 and size is returned.
 .PP
 .PD
 .PP
 When converting to the base integer types, if the integer is too large,
 the largest integer of the appropriate sign
 and size is returned.
 .PP

+When converting to and from floating point, results are rounded using IEEE 754 "round to nearest".
+If the integer is too large in magnitude,
+.I mptod 
+returns infinity of the appropriate sign.
+.PP

 The mathematical functions are:
 The mathematical functions are:

-.TF mpmagadd
+.TF mpfactorial

 .TP
 .I mpadd
 .BR "sum = b1 + b2" .
 .TP
 .I mpadd
 .BR "sum = b1 + b2" .


@@ -475,6 +585,76 @@ is less than, equal to, or greater than
 the same as
 .I mpcmp
 but ignores the sign and just compares magnitudes.
 the same as
 .I mpcmp
 but ignores the sign and just compares magnitudes.

+.TP
+.I mpsel
+assigns
+.I b1
+to
+.I res
+when
+.I s
+is not zero, otherwise
+.I b2
+is assigned to
+.IR res .
+.TP
+.I mpfactorial
+returns \fIn\fR!.
+.PD
+.PP
+Logical operations (treating negative numbers using two's complement):
+.TF mpxtend_
+.TP
+.I mpand
+.BR "res = b1 & b2" .
+.TP
+.I mpbic
+.BR "res = b1 & ~b2" .
+.TP
+.I mpor
+.BR "res = b1 | b2" .
+.TP
+.I mpxor
+.BR "res = b1 ^ b2" .
+.TP
+.I mpnot
+.BR "res = ~b1" .
+.TP
+.I mpasr
+.BR "res = b>>shift"
+(\fImpasr\fR, unlike
+.IR mpright ,
+uses two's complement).
+.TP
+.I mptrunc
+truncates
+.I b
+to 
+.I n
+bits and stores the result in
+.IR res .
+The result is never negative.
+.TP
+.I mpxtend
+truncates
+.I b
+to
+.I n
+bits, sign extends the MSB and stores the result in
+.IR res .
+.PD
+.PP
+Modular arithmetic:
+.TF mpmodmul_
+.TP
+.I mpmodadd    
+.BR "sum = b1+b2 mod m" .
+.TP
+.I mpmodsub    
+.BR "diff = b1-b2 mod m" .
+.TP
+.I mpmodmul    
+.BR "prod = b1*b2 mod m" .

 .PD
 .PP
 .I Mpextendedgcd
 .PD
 .PP
 .I Mpextendedgcd


@@ -498,7 +678,7 @@ are required to be positive.
 If called with negative arguments, it will
 return a gcd of 0.
 .PP
 If called with negative arguments, it will
 return a gcd of 0.
 .PP

-.I Mpinverse
+.I Mpinvert

 computes the multiplicative inverse of
 .I b
 .B mod
 computes the multiplicative inverse of
 .I b
 .B mod


@@ -548,13 +728,13 @@ We assume p has room for n+1 digits.
 .TP
 .I mpvecdigmulsub
 .BR "p[0:n] -= m * b[0:n-1]" .
 .TP
 .I mpvecdigmulsub
 .BR "p[0:n] -= m * b[0:n-1]" .

-This multiplies a an array of digits times a scalar and subtracts it fromo another array.
+This multiplies a an array of digits times a scalar and subtracts it from another array.

 We assume p has room for n+1 digits.  It returns +1 is the result is positive and
 -1 if negative.
 .TP
 .I mpvecmul
 We assume p has room for n+1 digits.  It returns +1 is the result is positive and
 -1 if negative.
 .TP
 .I mpvecmul

-.BR "p[0:alen*blen] = a[0:alen-1] * b[0:blen-1]" .
-We assume that p has room for alen*blen+1 digits.
+.BR "p[0:alen+blen] = a[0:alen-1] * b[0:blen-1]" .
+We assume that p has room for alen+blen+1 digits.

 .TP
 .I mpveccmp
 This returns -1, 0, or +1 as a - b is negative, 0, or positive.
 .TP
 .I mpveccmp
 This returns -1, 0, or +1 as a - b is negative, 0, or positive.


@@ -565,6 +745,17 @@ This returns -1, 0, or +1 as a - b is negative, 0, or positive.
 and
 .I mpzero
 are the constants 2, 1 and 0.  These cannot be freed.
 and
 .I mpzero
 are the constants 2, 1 and 0.  These cannot be freed.

+.SS "Time invariant computation"
+.PP
+In the field of cryptography, it is sometimes neccesary to implement
+algorithms such that the runtime of the algorithm is not depdenent on
+the input data. This library provides partial support for time
+invariant computation with the
+.I MPtimesafe
+flag that can be set on input or destination operands to request timing
+safe operation. The result of a timing safe operation will also have the
+.I MPtimesafe
+flag set and is not normalized.

 .SS "Chinese remainder theorem
 .PP
 When computing in a non-prime modulus, 
 .SS "Chinese remainder theorem
 .PP
 When computing in a non-prime modulus,