.TH MP 2.SH NAMEmpsetminbits, 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, mpfactorial, mpcmp, 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.B #include <libc.h>.br.B #include <mp.h>.PP.ta +\w'\fLCRTpre* \fP'u.Bmpint* mpnew(int n).PP.Bvoid mpfree(mpint *b).PP.Bvoid mpsetminbits(int n).PP.Bvoid mpbits(mpint *b, int n).PP.Bvoid mpnorm(mpint *b).PP.Bmpint* mpcopy(mpint *b).PP.Bvoid mpassign(mpint *old, mpint *new).PP.Bmpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b).PP.Bmpint* strtomp(char *buf, char **rptr, int base, mpint *b).PP.Bchar* mptoa(mpint *b, int base, char *buf, int blen).PP.Bint mpfmt(Fmt*).PP.Bmpint* betomp(uchar *buf, uint blen, mpint *b).PP.Bint mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp).PP.Bmpint* letomp(uchar *buf, uint blen, mpint *b).PP.Bint mptole(mpint *b, uchar *buf, uint blen, uchar **bufp).PP.Buint mptoui(mpint*).PP.Bmpint* uitomp(uint, mpint*).PP.Bint mptoi(mpint*).PP.Bmpint* itomp(int, mpint*).PP.Bmpint* vtomp(vlong, mpint*).PP.Bvlong mptov(mpint*).PP.Bmpint* uvtomp(uvlong, mpint*).PP.Buvlong mptouv(mpint*).PP.Bvoid mpadd(mpint *b1, mpint *b2, mpint *sum).PP.Bvoid mpmagadd(mpint *b1, mpint *b2, mpint *sum).PP.Bvoid mpsub(mpint *b1, mpint *b2, mpint *diff).PP.Bvoid mpmagsub(mpint *b1, mpint *b2, mpint *diff).PP.Bvoid mpleft(mpint *b, int shift, mpint *res).PP.Bvoid mpright(mpint *b, int shift, mpint *res).PP.Bvoid mpmul(mpint *b1, mpint *b2, mpint *prod).PP.Bvoid mpexp(mpint *b, mpint *e, mpint *m, mpint *res).PP.Bvoid mpmod(mpint *b, mpint *m, mpint *remainder).PP.Bvoid mpdiv(mpint *dividend, mpint *divisor, mpint *quotient,.br.B mpint *remainder).PP.Bmpint* mpfactorial(ulong n).PP.Bint mpcmp(mpint *b1, mpint *b2).PP.Bint mpmagcmp(mpint *b1, mpint *b2).PP.Bvoid mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x,.br.B mpint *y).PP.Bvoid mpinvert(mpint *b, mpint *m, mpint *res).PP.Bint mpsignif(mpint *b).PP.Bint mplowbits0(mpint *b).PP.Bvoid mpdigdiv(mpdigit *dividend, mpdigit divisor,.br.B mpdigit *quotient).PP.Bvoid mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen,.br.B mpdigit *sum).PP.Bvoid mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen,.br.B mpdigit *diff).PP.Bvoid mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p).PP.Bint mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p).PP.Bvoid mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,.br.B mpdigit *p).PP.Bint mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen).PP.BCRTpre* crtpre(int nfactors, mpint **factors).PP.BCRTres* crtin(CRTpre *crt, mpint *x).PP.Bvoid crtout(CRTpre *crt, CRTres *r, mpint *x).PP.Bvoid crtprefree(CRTpre *cre).PP.Bvoid crtresfree(CRTres *res).PP.Bmpint *mpzero, *mpone, *mptwo.DT.SH DESCRIPTIONThese routines perform extended precision integer arithmetic.The basic type is.BR mpint ,which points to an array of.BR mpdigit s,stored in little-endian order:.IP.EXtypedef struct mpint mpint;struct mpint{ int sign; /* +1 or -1 */ int size; /* allocated digits */ int top; /* significant digits */ mpdigit *p; char flags;};.EE.PPThe sign of 0 is +1..PPThe size of.B mpdigitis architecture-dependent and defined in.BR /$cputype/include/u.h ..BR Mpint sare dynamically allocated and must be explicitly freed. Operationsgrow the array of digits as needed..PPIn general, the result parameters are last in theargument list..PPRoutines that return an.B mpintwill allocate the.B mpintif the result parameter is.BR nil .This includes.IR strtomp ,.IR itomp ,.IR uitomp ,and.IR btomp .These functions, in addition to.I mpnewand.IR mpcopy ,will return.B nilif the allocation fails..PPInput and result parameters may point to the same.BR mpint .The routines check and copy where necessary..PP.I Mpnewcreates an.B mpintwith an initial allocation of.I nbits.If.I nis zero, the allocation will be whatever was specified in thelast call to.I mpsetminbitsor to the initial value, 1056..I Mpfreefrees an.BR mpint ..I Mpbitsgrows the allocation of.I bto fit at least.I nbits. If.B b->topdoesn't cover.I nbits,.I mpbitsincreases it to do so.Unless you are writing new basic operations, youcan restrict yourself to.B mpnew(0)and.BR mpfree(b) ..PP.I Mpnormnormalizes the representation by trimming any high order zerodigits. All routines except.B mpbitsreturn normalized results..PP.I Mpcopycreates a new.B mpintwith the same value as.I bwhile.I mpassignsets the value of.I newto be that of.IR old ..PP.I Mprandcreates an.I nbit random number using the generator.IR gen ..I Gentakes a pointer to a string of uchar's and the numberto fill in..PP.I Strtompand.I mptoaconvert between.SM ASCIIand.B mpintrepresentations using the base indicated.Only the bases 10, 16, 32, and 64 aresupported. Anything else defaults to 16..IR Strtompskips any leading spaces or tabs..IR Strtomp 'sscan stops when encountering a digit not valid in thebase. If.I rptris not zero,.I *rptris set to point to the character immediately after thestring converted.If the parse pterminates before any digits are found,.I strtompreturn.BR nil ..I Mptoareturns a pointer to the filled buffer.If the parameter.I bufis.BR nil ,the buffer is allocated..I Mpfmtcan be used with.IR fmtinstall (2)and.IR print (2)to print hexadecimal representations of.BR mpint s.The conventional verb is.LR B ,for which.I mp.hprovides a.LR pragma ..PP.I Mptobeand.I mptoleconvert an.I mpintto a byte array. The former creates a big endian representation,the latter a little endian one.If the destination.I bufis not.BR nil ,it specifies the buffer of length.I blenfor the result. If the representationis less than.I blenbytes, the rest of the buffer is zero filled.If.I bufis.BR nil ,then a buffer is allocated and a pointer to it isdeposited in the location pointed to by.IR bufp .Sign is ignored in these conversions, i.e., the bytearray version is always positive..PP.IR Betomp ,and.I letompconvert from a big or little endian byte array at.I bufof length.I blento an.IR mpint .If.I bis not.IR nil ,it refers to a preallocated.I mpintfor the result.If.I bis.BR nil ,a new integer is allocated and returned as the result..PPThe integer conversions are:.TF Mptouv.TP.I mptoui.BR mpint -> "unsigned int".TP.I uitomp.BR "unsigned int" -> mpint.TP.I mptoi.BR mpint -> "int".TP.I itomp.BR "int" -> mpint.TP.I mptouv.BR mpint -> "unsigned vlong".TP.I uvtomp.BR "unsigned vlong" -> mpint.TP.I mptov.BR mpint -> "vlong".TP.I vtomp.BR "vlong" -> mpint.PD.PPWhen converting to the base integer types, if the integer is too large,the largest integer of the appropriate signand size is returned..PPThe mathematical functions are:.TF mpmagadd.TP.I mpadd.BR "sum = b1 + b2" ..TP.I mpmagadd.BR "sum = abs(b1) + abs(b2)" . .TP.I mpsub.BR "diff = b1 - b2" ..TP.I mpmagsub.BR "diff = abs(b1) - abs(b2)" ..TP.I mpleft.BR "res = b<<shift" ..TP.I mpright.BR "res = b>>shift" ..TP.I mpmul.BR "prod = b1*b2" ..TP.I mpexpif.I mis nil,.BR "res = b**e" .Otherwise,.BR "res = b**e mod m" ..TP.I mpmod.BR "remainder = b % m" ..TP.I mpdiv.BR "quotient = dividend/divisor" ..BR "remainder = dividend % divisor" ..TP.I mpfactorialReturn a newly allocated.BR "fact = n!" ..I mpcmpreturns -1, 0, or +1 as.I b1is less than, equal to, or greater than.IR b2 ..TP.I mpmagcmpthe same as.I mpcmpbut ignores the sign and just compares magnitudes..PD.PP.I Mpextendedgcdcomputes the greatest common denominator,.IR d ,of.I aand.IR b .It also computes.I xand.I ysuch that.BR "a*x + b*y = d" .Both.I aLines 1–500 of 616. Load more
.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, mpfactorial, mpcmp, 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 .B #include <libc.h> .br .B #include <mp.h> .PP .ta +\w'\fLCRTpre* \fP'u .B mpint* mpnew(int n) .PP .B void mpfree(mpint *b) .PP .B void mpsetminbits(int n) .PP .B void mpbits(mpint *b, int n) .PP .B void mpnorm(mpint *b) .PP .B mpint* mpcopy(mpint *b) .PP .B void mpassign(mpint *old, mpint *new) .PP .B mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b) .PP .B mpint* strtomp(char *buf, char **rptr, int base, mpint *b) .PP .B char* mptoa(mpint *b, int base, char *buf, int blen) .PP .B int mpfmt(Fmt*) .PP .B mpint* betomp(uchar *buf, uint blen, mpint *b) .PP .B int mptobe(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 uint mptoui(mpint*) .PP .B mpint* uitomp(uint, mpint*) .PP .B int mptoi(mpint*) .PP .B mpint* itomp(int, mpint*) .PP .B mpint* vtomp(vlong, mpint*) .PP .B vlong mptov(mpint*) .PP .B mpint* uvtomp(uvlong, mpint*) .PP .B uvlong mptouv(mpint*) .PP .B void mpadd(mpint *b1, mpint *b2, mpint *sum) .PP .B void mpmagadd(mpint *b1, mpint *b2, mpint *sum) .PP .B void mpsub(mpint *b1, mpint *b2, mpint *diff) .PP .B void mpmagsub(mpint *b1, mpint *b2, mpint *diff) .PP .B void mpleft(mpint *b, int shift, mpint *res) .PP .B void mpright(mpint *b, int shift, mpint *res) .PP .B void mpmul(mpint *b1, mpint *b2, mpint *prod) .PP .B void mpexp(mpint *b, mpint *e, mpint *m, mpint *res) .PP .B void mpmod(mpint *b, mpint *m, mpint *remainder) .PP .B void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, .br .B mpint *remainder) .PP .B mpint* mpfactorial(ulong n) .PP .B int mpcmp(mpint *b1, mpint *b2) .PP .B int mpmagcmp(mpint *b1, mpint *b2) .PP .B void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, .br .B mpint *y) .PP .B void mpinvert(mpint *b, mpint *m, mpint *res) .PP .B int mpsignif(mpint *b) .PP .B int mplowbits0(mpint *b) .PP .B void mpdigdiv(mpdigit *dividend, mpdigit divisor, .br .B mpdigit *quotient) .PP .B void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, .br .B mpdigit *sum) .PP .B void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, .br .B mpdigit *diff) .PP .B void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p) .PP .B int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p) .PP .B void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, .br .B mpdigit *p) .PP .B int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen) .PP .B CRTpre* crtpre(int nfactors, mpint **factors) .PP .B CRTres* crtin(CRTpre *crt, mpint *x) .PP .B void crtout(CRTpre *crt, CRTres *r, mpint *x) .PP .B void crtprefree(CRTpre *cre) .PP .B void crtresfree(CRTres *res) .PP .B mpint *mpzero, *mpone, *mptwo .DT .SH DESCRIPTION These routines perform extended precision integer arithmetic. The basic type is .BR mpint , which points to an array of .BR mpdigit s, stored in little-endian order: .IP .EX typedef struct mpint mpint; struct mpint { int sign; /* +1 or -1 */ int size; /* allocated digits */ int top; /* significant digits */ mpdigit *p; char flags; }; .EE .PP The sign of 0 is +1. .PP The size of .B mpdigit is architecture-dependent and defined in .BR /$cputype/include/u.h . .BR Mpint s are dynamically allocated and must be explicitly freed. Operations grow the array of digits as needed. .PP In general, the result parameters are last in the argument list. .PP Routines that return an .B mpint will allocate the .B mpint if the result parameter is .BR nil . This includes .IR strtomp , .IR itomp , .IR uitomp , and .IR btomp . These functions, in addition to .I mpnew and .IR mpcopy , will return .B nil if the allocation fails. .PP Input and result parameters may point to the same .BR mpint . The routines check and copy where necessary. .PP .I Mpnew creates an .B mpint with an initial allocation of .I n bits. If .I n is zero, the allocation will be whatever was specified in the last call to .I mpsetminbits or to the initial value, 1056. .I Mpfree frees an .BR mpint . .I Mpbits grows the allocation of .I b to fit at least .I n bits. If .B b->top doesn't cover .I n bits, .I mpbits increases it to do so. Unless you are writing new basic operations, you can restrict yourself to .B mpnew(0) and .BR mpfree(b) . .PP .I Mpnorm normalizes the representation by trimming any high order zero digits. All routines except .B mpbits return normalized results. .PP .I Mpcopy creates a new .B mpint with the same value as .I b while .I mpassign sets the value of .I new to be that of .IR old . .PP .I Mprand creates an .I n bit random number using the generator .IR gen . .I Gen takes a pointer to a string of uchar's and the number to fill in. .PP .I Strtomp and .I mptoa convert between .SM ASCII and .B mpint representations using the base indicated. Only the bases 10, 16, 32, and 64 are supported. Anything else defaults to 16. .IR Strtomp skips any leading spaces or tabs. .IR Strtomp 's scan stops when encountering a digit not valid in the base. If .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, .I strtomp return .BR nil . .I Mptoa returns a pointer to the filled buffer. If the parameter .I buf is .BR nil , the buffer is allocated. .I Mpfmt can be used with .IR fmtinstall (2) and .IR print (2) to print hexadecimal representations of .BR mpint s. The conventional verb is .LR B , for which .I mp.h provides a .LR pragma . .PP .I Mptobe and .I mptole convert an .I mpint to a byte array. The former creates a big endian representation, the latter a little endian one. If the destination .I buf is not .BR nil , it specifies the buffer of length .I blen for the result. If the representation is less than .I blen bytes, the rest of the buffer is zero filled. If .I buf is .BR nil , then a buffer is allocated and a pointer to it is deposited in the location pointed to by .IR bufp . Sign is ignored in these conversions, i.e., the byte array version is always positive. .PP .IR Betomp , and .I letomp convert from a big or little endian byte array at .I buf of length .I blen to an .IR mpint . If .I b is not .IR nil , it refers to a preallocated .I mpint for the result. If .I b is .BR nil , a new integer is allocated and returned as the result. .PP The integer conversions are: .TF Mptouv .TP .I mptoui .BR mpint -> "unsigned int" .TP .I uitomp .BR "unsigned int" -> mpint .TP .I mptoi .BR mpint -> "int" .TP .I itomp .BR "int" -> mpint .TP .I mptouv .BR mpint -> "unsigned vlong" .TP .I uvtomp .BR "unsigned vlong" -> mpint .TP .I mptov .BR mpint -> "vlong" .TP .I vtomp .BR "vlong" -> 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 The mathematical functions are: .TF mpmagadd .TP .I mpadd .BR "sum = b1 + b2" . .TP .I mpmagadd .BR "sum = abs(b1) + abs(b2)" . .TP .I mpsub .BR "diff = b1 - b2" . .TP .I mpmagsub .BR "diff = abs(b1) - abs(b2)" . .TP .I mpleft .BR "res = b<<shift" . .TP .I mpright .BR "res = b>>shift" . .TP .I mpmul .BR "prod = b1*b2" . .TP .I mpexp if .I m is nil, .BR "res = b**e" . Otherwise, .BR "res = b**e mod m" . .TP .I mpmod .BR "remainder = b % m" . .TP .I mpdiv .BR "quotient = dividend/divisor" . .BR "remainder = dividend % divisor" . .TP .I mpfactorial Return a newly allocated .BR "fact = n!" . .I mpcmp returns -1, 0, or +1 as .I b1 is less than, equal to, or greater than .IR b2 . .TP .I mpmagcmp the same as .I mpcmp but ignores the sign and just compares magnitudes. .PD .PP .I Mpextendedgcd computes the greatest common denominator, .IR d , of .I a and .IR b . It also computes .I x and .I y such that .BR "a*x + b*y = d" . Both .I a