ref: 67e8be8642a885c06881deed932613c35ebf5dc0
parent: 61c977fbe25def632a3f351a44ed1ede1f0477f4
author: Sigrid Solveig Haflínudóttir <ftrvxmtrx@gmail.com>
date: Fri Feb 18 20:01:05 EST 2022
pc(1) port
--- /dev/null
+++ b/.gitignore
@@ -1,0 +1,3 @@
+*.o
+pc
+pc.c
--- /dev/null
+++ b/Makefile
@@ -1,0 +1,97 @@
+TARGET = pc
+PREFIX ?= /usr/local
+CFLAGS ?= -O2 -Iinclude -Wno-incompatible-pointer-types -Wno-microsoft-anon-tag -fms-extensions
+
+OFILES=\
+ libc/dofmt.o\
+ libc/dorfmt.o\
+ libc/encodefmt.o\
+ libc/fltfmt.o\
+ libc/fmt.o\
+ libc/fmtfd.o\
+ libc/fmtfdflush.o\
+ libc/fmtlock.o\
+ libc/fmtprint.o\
+ libc/fmtquote.o\
+ libc/fmtrune.o\
+ libc/fmtstr.o\
+ libc/fmtvprint.o\
+ libc/fprint.o\
+ libc/genrandom.o\
+ libc/mallocz.o\
+ libc/nan64.o\
+ libc/print.o\
+ libc/rune.o\
+ libc/snprint.o\
+ libc/sprint.o\
+ libc/strtod.o\
+ libc/sysfatal.o\
+ libc/u16.o\
+ libc/u32.o\
+ libc/u64.o\
+ libc/utflen.o\
+ libc/vfprint.o\
+ libc/vsnprint.o\
+ libmp/betomp.o\
+ libmp/cnfield.o\
+ libmp/gmfield.o\
+ libmp/letomp.o\
+ libmp/mpadd.o\
+ libmp/mpaux.o\
+ libmp/mpcmp.o\
+ libmp/mpdigdiv.o\
+ libmp/mpdiv.o\
+ libmp/mpexp.o\
+ libmp/mpextendedgcd.o\
+ libmp/mpfield.o\
+ libmp/mpfmt.o\
+ libmp/mpinvert.o\
+ libmp/mpleft.o\
+ libmp/mplogic.o\
+ libmp/mpmod.o\
+ libmp/mpmodop.o\
+ libmp/mpmul.o\
+ libmp/mpnrand.o\
+ libmp/mprand.o\
+ libmp/mpright.o\
+ libmp/mpsel.o\
+ libmp/mpsub.o\
+ libmp/mptobe.o\
+ libmp/mptober.o\
+ libmp/mptoi.o\
+ libmp/mptole.o\
+ libmp/mptolel.o\
+ libmp/mptoui.o\
+ libmp/mptouv.o\
+ libmp/mptov.o\
+ libmp/mpvecadd.o\
+ libmp/mpveccmp.o\
+ libmp/mpvecdigmuladd.o\
+ libmp/mpvecsub.o\
+ libmp/mpvectscmp.o\
+ libmp/strtomp.o\
+ pc.o\
+
+.PHONY: all default install uninstall clean
+
+all: default
+
+default: $(TARGET)
+
+install: $(TARGET)
+ install -d $(DESTDIR)$(PREFIX)/bin
+ install -m 755 $(TARGET) $(DESTDIR)$(PREFIX)/bin
+ install -d $(DESTDIR)$(PREFIX)/share/man/man1
+ install -m 644 pc.1 $(DESTDIR)$(PREFIX)/share/man/man1
+
+uninstall:
+ rm -f $(TARGET) $(DESTDIR)$(PREFIX)/bin/$(TARGET) $(DESTDIR)$(PREFIX)/share/man/man1/pc.1
+
+clean:
+ rm -f $(TARG) $(OFILES) pc.c
+
+$(TARGET): $(OFILES)
+
+pc.o: pc.c
+
+pc.c: pc.y
--- /dev/null
+++ b/include/9windows.h
@@ -1,0 +1,21 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include <fcntl.h>
+#include <io.h>
+#include <setjmp.h>
+#include <direct.h>
+#include <process.h>
+#include <time.h>
+#include <assert.h>
+#include <stdarg.h>
+
+/* disable various silly warnings */
+#ifdef MSVC
+#pragma warning( disable : 4245 4305 4244 4102 4761 4090 4028 4024)
+#endif
+
+typedef __int64 p9_vlong;
+typedef unsigned __int64 p9_uvlong;
+typedef unsigned uintptr;
--- /dev/null
+++ b/include/bio.h
@@ -1,0 +1,27 @@
+#include <stdio.h>
+
+typedef FILE Biobufhdr;
+typedef Biobufhdr Biobuf;
+
+static uint8_t lastc;
+
+static int
+Bgetc(Biobufhdr *bp)
+{+ lastc = fgetc(bp);
+ return feof(bp) ? -1 : lastc;
+}
+
+static int
+Bungetc(Biobufhdr *bp)
+{+ ungetc(lastc, bp);
+ lastc = 0;
+ return 0;
+}
+
+static Biobufhdr *
+Bfdopen(int f, int mode)
+{+ return stdin;
+}
--- /dev/null
+++ b/include/dtos.h
@@ -1,0 +1,15 @@
+#if defined(linux) || defined(IRIX) || defined(SOLARIS) || defined(OSF1) || defined(__FreeBSD__) || defined(__APPLE__) || defined(__NetBSD__) || defined(__sun) || defined(sun) || defined(__OpenBSD__) || defined(__DragonFly__) || defined(__EMSCRIPTEN__)
+# include "unix.h"
+# ifdef __APPLE__
+# define panic dt_panic
+# endif
+#elif defined(WINDOWS)
+# include "9windows.h"
+# define main mymain
+#else
+# error "Define an OS"
+#endif
+
+#ifdef IRIX
+typedef int socklen_t;
+#endif
--- /dev/null
+++ b/include/lib.h
@@ -1,0 +1,315 @@
+/* avoid name conflicts */
+#define accept pm_accept
+#define listen pm_listen
+#define sleep ksleep
+#define wakeup kwakeup
+#ifdef strtod
+#undef strtod
+#endif
+#define strtod fmtstrtod
+
+/* conflicts on some os's */
+#define encrypt libencrypt
+#define decrypt libdecrypt
+#define oserror liboserror
+#define clone libclone
+#define atexit libatexit
+#define log2 liblog2
+#define log liblog
+#define reboot libreboot
+#define strtoll libstrtoll
+#undef timeradd
+#define timeradd xtimeradd
+#define gmtime libgmtime
+
+
+#define nil ((void*)0)
+
+typedef unsigned char p9_uchar;
+typedef unsigned int p9_uint;
+typedef unsigned int p9_ulong;
+typedef int p9_long;
+typedef signed char p9_schar;
+typedef unsigned short p9_ushort;
+typedef unsigned int Rune;
+typedef unsigned int p9_u32int;
+typedef unsigned long long p9_u64int;
+typedef p9_u32int mpdigit;
+
+/* make sure we don't conflict with predefined types */
+#define schar p9_schar
+#define uchar p9_uchar
+#define ushort p9_ushort
+#define uint p9_uint
+#define u32int p9_u32int
+#define u64int p9_u64int
+
+/* #define long int rather than p9_long so that "unsigned long" is valid */
+#define long int
+#define ulong p9_ulong
+#define vlong p9_vlong
+#define uvlong p9_uvlong
+
+#define nelem(x) (sizeof(x)/sizeof((x)[0]))
+#define SET(x) ((x)=0)
+#define USED(x) if(x);else
+
+enum
+{+ UTFmax = 4, /* maximum bytes per rune */
+ Runesync = 0x80, /* cannot represent part of a UTF sequence (<) */
+ Runeself = 0x80, /* rune and UTF sequences are the same (<) */
+ Runeerror = 0xFFFD, /* decoding error in UTF */
+ Runemax = 0x10FFFF, /* 21-bit rune */
+ Runemask = 0x1FFFFF, /* bits used by runes (see grep) */
+};
+
+/*
+ * new rune routines
+ */
+extern int runetochar(char*, Rune*);
+extern int chartorune(Rune*, char*);
+extern int runelen(long);
+extern int fullrune(char*, int);
+
+extern int wstrtoutf(char*, Rune*, int);
+extern int wstrutflen(Rune*);
+
+/*
+ * rune routines from converted str routines
+ */
+extern long utflen(char*);
+extern char* utfrune(char*, long);
+extern char* utfrrune(char*, long);
+
+/*
+ * Syscall data structures
+ */
+#define MORDER 0x0003 /* mask for bits defining order of mounting */
+#define MREPL 0x0000 /* mount replaces object */
+#define MBEFORE 0x0001 /* mount goes before others in union directory */
+#define MAFTER 0x0002 /* mount goes after others in union directory */
+#define MCREATE 0x0004 /* permit creation in mounted directory */
+#define MCACHE 0x0010 /* cache some data */
+#define MMASK 0x0017 /* all bits on */
+
+#define OREAD 0 /* open for read */
+#define OWRITE 1 /* write */
+#define ORDWR 2 /* read and write */
+#define OEXEC 3 /* execute, == read but check execute permission */
+#define OTRUNC 16 /* or'ed in (except for exec), truncate file first */
+#define OCEXEC 32 /* or'ed in, close on exec */
+#define ORCLOSE 64 /* or'ed in, remove on close */
+#define OEXCL 0x1000 /* or'ed in, exclusive create */
+
+#define NCONT 0 /* continue after note */
+#define NDFLT 1 /* terminate after note */
+#define NSAVE 2 /* clear note but hold state */
+#define NRSTR 3 /* restore saved state */
+
+#define ERRMAX 128 /* max length of error string */
+#define KNAMELEN 28 /* max length of name held in kernel */
+
+/* bits in Qid.type */
+#define QTDIR 0x80 /* type bit for directories */
+#define QTAPPEND 0x40 /* type bit for append only files */
+#define QTEXCL 0x20 /* type bit for exclusive use files */
+#define QTMOUNT 0x10 /* type bit for mounted channel */
+#define QTAUTH 0x08 /* type bit for authentication file */
+#define QTFILE 0x00 /* plain file */
+
+/* bits in Dir.mode */
+#define DMDIR 0x80000000 /* mode bit for directories */
+#define DMAPPEND 0x40000000 /* mode bit for append only files */
+#define DMEXCL 0x20000000 /* mode bit for exclusive use files */
+#define DMMOUNT 0x10000000 /* mode bit for mounted channel */
+#define DMAUTH 0x08000000 /* mode bit for authentication files */
+#define DMREAD 0x4 /* mode bit for read permission */
+#define DMWRITE 0x2 /* mode bit for write permission */
+#define DMEXEC 0x1 /* mode bit for execute permission */
+
+typedef struct Lock
+{+#ifdef PTHREAD
+ int init;
+ pthread_mutex_t mutex;
+#else
+ int key;
+#endif
+} Lock;
+
+typedef struct QLock
+{+ Lock lk;
+ struct Proc *hold;
+ struct Proc *first;
+ struct Proc *last;
+} QLock;
+
+typedef
+struct Qid
+{+ uvlong path;
+ ulong vers;
+ uchar type;
+} Qid;
+
+typedef
+struct Dir {+ /* system-modified data */
+ ushort type; /* server type */
+ uint dev; /* server subtype */
+ /* file data */
+ Qid qid; /* unique id from server */
+ ulong mode; /* permissions */
+ ulong atime; /* last read time */
+ ulong mtime; /* last write time */
+ vlong length; /* file length */
+ char *name; /* last element of path */
+ char *uid; /* owner name */
+ char *gid; /* group name */
+ char *muid; /* last modifier name */
+} Dir;
+
+typedef
+struct Waitmsg
+{+ int pid; /* of loved one */
+ ulong time[3]; /* of loved one & descendants */
+ char *msg;
+} Waitmsg;
+
+/*
+ * print routines
+ */
+typedef struct Fmt Fmt;
+struct Fmt{+ uchar runes; /* output buffer is runes or chars? */
+ void *start; /* of buffer */
+ void *to; /* current place in the buffer */
+ void *stop; /* end of the buffer; overwritten if flush fails */
+ int (*flush)(Fmt *); /* called when to == stop */
+ void *farg; /* to make flush a closure */
+ int nfmt; /* num chars formatted so far */
+ va_list args; /* args passed to dofmt */
+ int r; /* % format Rune */
+ int width;
+ int prec;
+ ulong flags;
+};
+
+enum{+ FmtWidth = 1,
+ FmtLeft = FmtWidth << 1,
+ FmtPrec = FmtLeft << 1,
+ FmtSharp = FmtPrec << 1,
+ FmtSpace = FmtSharp << 1,
+ FmtSign = FmtSpace << 1,
+ FmtZero = FmtSign << 1,
+ FmtUnsigned = FmtZero << 1,
+ FmtShort = FmtUnsigned << 1,
+ FmtLong = FmtShort << 1,
+ FmtVLong = FmtLong << 1,
+ FmtComma = FmtVLong << 1,
+ FmtByte = FmtComma << 1,
+
+ FmtFlag = FmtByte << 1,
+ FmtLDouble = FmtFlag << 1
+};
+
+extern int print(char*, ...);
+extern char* seprint(char*, char*, char*, ...);
+extern char* vseprint(char*, char*, char*, va_list);
+extern int snprint(char*, int, char*, ...);
+extern int vsnprint(char*, int, char*, va_list);
+extern char* smprint(char*, ...);
+extern char* vsmprint(char*, va_list);
+extern int sprint(char*, char*, ...);
+extern int fprint(int, char*, ...);
+extern int vfprint(int, char*, va_list);
+
+extern int (*doquote)(int);
+extern int runesprint(Rune*, char*, ...);
+extern int runesnprint(Rune*, int, char*, ...);
+extern int runevsnprint(Rune*, int, char*, va_list);
+extern Rune* runeseprint(Rune*, Rune*, char*, ...);
+extern Rune* runevseprint(Rune*, Rune*, char*, va_list);
+extern Rune* runesmprint(char*, ...);
+extern Rune* runevsmprint(char*, va_list);
+
+extern Rune* runestrchr(Rune*, Rune);
+extern long runestrlen(Rune*);
+extern Rune* runestrstr(Rune*, Rune*);
+
+extern int fmtfdinit(Fmt*, int, char*, int);
+extern int fmtfdflush(Fmt*);
+extern int fmtstrinit(Fmt*);
+extern int fmtinstall(int, int (*)(Fmt*));
+extern char* fmtstrflush(Fmt*);
+extern int runefmtstrinit(Fmt*);
+extern Rune* runefmtstrflush(Fmt*);
+extern int fmtstrcpy(Fmt*, char*);
+extern int fmtprint(Fmt*, char*, ...);
+extern int fmtvprint(Fmt*, char*, va_list);
+extern void* mallocz(ulong, int);
+extern int fmtrune(Fmt *f, int r);
+
+#define getcallerpc(v) 0
+extern char* cleanname(char*);
+extern void sysfatal(char*, ...);
+extern char* strecpy(char*, char*, char*);
+
+extern int tokenize(char*, char**, int);
+extern int getfields(char*, char**, int, int, char*);
+extern char* utfecpy(char*, char*, char*);
+extern int tas(int*);
+extern void quotefmtinstall(void);
+extern int dec64(uchar*, int, char*, int);
+extern int enc64(char*, int, uchar*, int);
+extern int dec32(uchar*, int, char*, int);
+extern int enc32(char*, int, uchar*, int);
+extern int dec16(uchar*, int, char*, int);
+extern int enc16(char*, int, uchar*, int);
+extern int dec64chr(int);
+extern int enc64chr(int);
+extern int dec32chr(int);
+extern int enc32chr(int);
+extern int dec16chr(int);
+extern int enc16chr(int);
+extern int encodefmt(Fmt*);
+void hnputs(void *p, unsigned short v);
+extern int dofmt(Fmt*, char*);
+extern double __NaN(void);
+extern int __isNaN(double);
+extern double strtod(const char*, char**);
+extern vlong strtoll(const char *, char **, int);
+extern int utfnlen(char*, long);
+extern double __Inf(int);
+extern int __isInf(double, int);
+
+extern int (*fmtdoquote)(int);
+
+extern void exits(char*);
+extern long readn(int, void*, long);
+
+extern void genrandom(uchar *buf, int nbytes);
+
+/*
+ * Time-of-day
+ */
+
+typedef
+struct Tm
+{+ int sec;
+ int min;
+ int hour;
+ int mday;
+ int mon;
+ int year;
+ int wday;
+ int yday;
+ char zone[4];
+ int tzoff;
+} Tm;
+extern Tm* gmtime(long);
--- /dev/null
+++ b/include/libc.h
@@ -1,0 +1,6 @@
+#include "lib.h"
+#define setmalloctag(a,b)
+#define qlock(x) ((void)(x))
+#define qunlock(x) ((void)(x))
+#define lock(x) ((void)(x))
+#define unlock(x) ((void)(x))
--- /dev/null
+++ b/include/mp.h
@@ -1,0 +1,176 @@
+#define _MPINT 1
+
+/*
+ * the code assumes mpdigit to be at least an int
+ * mpdigit must be an atomic type. mpdigit is defined
+ * in the architecture specific u.h
+ */
+typedef struct mpint mpint;
+
+struct mpint
+{+ int sign; /* +1 or -1 */
+ int size; /* allocated digits */
+ int top; /* significant digits */
+ mpdigit *p;
+ char flags;
+};
+
+enum
+{+ MPstatic= 0x01, /* static constant */
+ MPnorm= 0x02, /* normalization status */
+ MPtimesafe= 0x04, /* request time invariant computation */
+ MPfield= 0x08, /* this mpint is a field modulus */
+
+ Dbytes= sizeof(mpdigit), /* bytes per digit */
+ Dbits= Dbytes*8 /* bits per digit */
+};
+
+/* allocation */
+void mpsetminbits(int n); /* newly created mpint's get at least n bits */
+mpint* mpnew(int n); /* create a new mpint with at least n bits */
+void mpfree(mpint *b);
+void mpbits(mpint *b, int n); /* ensure that b has at least n bits */
+mpint* mpnorm(mpint *b); /* dump leading zeros */
+mpint* mpcopy(mpint *b);
+void mpassign(mpint *old, mpint *new);
+
+/* random bits */
+mpint* mprand(int bits, void (*gen)(uchar*, int), mpint *b);
+/* return uniform random [0..n-1] */
+mpint* mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b);
+
+/* conversion */
+mpint* strtomp(char*, char**, int, mpint*); /* ascii */
+int mpfmt(Fmt*);
+char* mptoa(mpint*, int, char*, int);
+mpint* letomp(uchar*, uint, mpint*); /* byte array, little-endian */
+int mptole(mpint*, uchar*, uint, uchar**);
+void mptolel(mpint *b, uchar *p, int n);
+mpint* betomp(uchar*, uint, mpint*); /* byte array, big-endian */
+int mptobe(mpint*, uchar*, uint, uchar**);
+void mptober(mpint *b, uchar *p, int n);
+uint mptoui(mpint*); /* unsigned int */
+mpint* uitomp(uint, mpint*);
+int mptoi(mpint*); /* int */
+mpint* itomp(int, mpint*);
+uvlong mptouv(mpint*); /* unsigned vlong */
+mpint* uvtomp(uvlong, mpint*);
+vlong mptov(mpint*); /* vlong */
+mpint* vtomp(vlong, mpint*);
+
+/* divide 2 digits by one */
+void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
+
+/* in the following, the result mpint may be */
+/* the same as one of the inputs. */
+void mpadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
+void mpsub(mpint *b1, mpint *b2, mpint *diff); /* diff = b1-b2 */
+void mpleft(mpint *b, int shift, mpint *res); /* res = b<<shift */
+void mpright(mpint *b, int shift, mpint *res); /* res = b>>shift */
+void mpmul(mpint *b1, mpint *b2, mpint *prod); /* prod = b1*b2 */
+void mpexp(mpint *b, mpint *e, mpint *m, mpint *res); /* res = b**e mod m */
+void mpmod(mpint *b, mpint *m, mpint *remainder); /* remainder = b mod m */
+
+/* logical operations */
+void mpand(mpint *b1, mpint *b2, mpint *res);
+void mpbic(mpint *b1, mpint *b2, mpint *res);
+void mpor(mpint *b1, mpint *b2, mpint *res);
+void mpnot(mpint *b, mpint *res);
+void mpxor(mpint *b1, mpint *b2, mpint *res);
+void mptrunc(mpint *b, int n, mpint *res);
+void mpxtend(mpint *b, int n, mpint *res);
+void mpasr(mpint *b, int shift, mpint *res);
+
+/* modular arithmetic, time invariant when 0≤b1≤m-1 and 0≤b2≤m-1 */
+void mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum); /* sum = b1+b2 % m */
+void mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff); /* diff = b1-b2 % m */
+void mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod); /* prod = b1*b2 % m */
+
+/* quotient = dividend/divisor, remainder = dividend % divisor */
+void mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder);
+
+/* return neg, 0, pos as b1-b2 is neg, 0, pos */
+int mpcmp(mpint *b1, mpint *b2);
+
+/* res = s != 0 ? b1 : b2 */
+void mpsel(int s, mpint *b1, mpint *b2, mpint *res);
+
+/* extended gcd return d, x, and y, s.t. d = gcd(a,b) and ax+by = d */
+void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y);
+
+/* res = b**-1 mod m */
+void mpinvert(mpint *b, mpint *m, mpint *res);
+
+/* bit counting */
+int mpsignif(mpint*); /* number of sigificant bits in mantissa */
+int mplowbits0(mpint*); /* k, where n = 2**k * q for odd q */
+
+/* well known constants */
+extern mpint *mpzero, *mpone, *mptwo;
+
+/* sum[0:alen] = a[0:alen-1] + b[0:blen-1] */
+/* prereq: alen >= blen, sum has room for alen+1 digits */
+void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum);
+
+/* diff[0:alen-1] = a[0:alen-1] - b[0:blen-1] */
+/* prereq: alen >= blen, diff has room for alen digits */
+void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff);
+
+/* p[0:n] += m * b[0:n-1] */
+/* prereq: p has room for n+1 digits */
+void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p);
+
+/* p[0:n] -= m * b[0:n-1] */
+/* prereq: p has room for n+1 digits */
+int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p);
+
+/* p[0:alen+blen-1] = a[0:alen-1] * b[0:blen-1] */
+/* prereq: alen >= blen, p has room for m*n digits */
+void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
+void mpvectsmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p);
+
+/* sign of a - b or zero if the same */
+int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen);
+int mpvectscmp(mpdigit *a, int alen, mpdigit *b, int blen);
+
+/* divide the 2 digit dividend by the one digit divisor and stick in quotient */
+/* we assume that the result is one digit - overflow is all 1's */
+void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient);
+
+/* playing with magnitudes */
+int mpmagcmp(mpint *b1, mpint *b2);
+void mpmagadd(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
+void mpmagsub(mpint *b1, mpint *b2, mpint *sum); /* sum = b1+b2 */
+
+/* chinese remainder theorem */
+typedef struct CRTpre CRTpre; /* precomputed values for converting */
+ /* twixt residues and mpint */
+typedef struct CRTres CRTres; /* residue form of an mpint */
+
+struct CRTres
+{+ int n; /* number of residues */
+ mpint *r[1]; /* residues */
+};
+
+CRTpre* crtpre(int, mpint**); /* precompute conversion values */
+CRTres* crtin(CRTpre*, mpint*); /* convert mpint to residues */
+void crtout(CRTpre*, CRTres*, mpint*); /* convert residues to mpint */
+void crtprefree(CRTpre*);
+void crtresfree(CRTres*);
+
+/* fast field arithmetic */
+typedef struct Mfield Mfield;
+
+struct Mfield
+{+ mpint m;
+ int (*reduce)(Mfield*, mpint*, mpint*);
+};
+
+mpint *mpfield(mpint*);
+
+Mfield *gmfield(mpint*);
+Mfield *cnfield(mpint*);
--- /dev/null
+++ b/include/thread.h
@@ -1,0 +1,17 @@
+typedef struct Ref Ref;
+
+struct Ref {+ long ref;
+};
+
+static void
+incref(Ref *r)
+{+ r->ref++;
+}
+
+static long
+decref(Ref *r)
+{+ return --(r->ref);
+}
--- /dev/null
+++ b/include/u.h
@@ -1,0 +1,29 @@
+#include "dtos.h"
+
+/* avoid name conflicts */
+#undef accept
+#undef listen
+
+/* sys calls */
+#undef bind
+#undef chdir
+#undef close
+#undef create
+#undef dup
+#undef export
+#undef fstat
+#undef fwstat
+#undef mount
+#undef open
+#undef start
+#undef read
+#undef remove
+#undef seek
+#undef stat
+#undef write
+#undef wstat
+#undef unmount
+#undef pipe
+#undef iounit
+
+#define EXPORT EMSCRIPTEN_KEEPALIVE
--- /dev/null
+++ b/include/unix.h
@@ -1,0 +1,46 @@
+#undef _FORTIFY_SOURCE /* stupid ubuntu warnings */
+#define __BSD_VISIBLE 1 /* FreeBSD 5.x */
+#define _BSD_SOURCE 1
+#define _NETBSD_SOURCE 1 /* NetBSD */
+#define _SVID_SOURCE 1
+#define _DEFAULT_SOURCE 1
+#if !defined(__APPLE__) && !defined(__OpenBSD__)
+# ifndef _XOPEN_SOURCE
+# define _XOPEN_SOURCE 1000
+# endif
+# ifndef _XOPEN_SOURCE_EXTENDED
+# define _XOPEN_SOURCE_EXTENDED 1
+# endif
+#endif
+#define _LARGEFILE64_SOURCE 1
+#define _FILE_OFFSET_BITS 64
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include <fcntl.h>
+#include <setjmp.h>
+#include <stddef.h>
+#include <time.h>
+#include <assert.h>
+#include <unistd.h>
+#include <stdarg.h>
+#include <inttypes.h>
+#include <ctype.h>
+#include <errno.h>
+#ifdef PTHREAD
+#include <pthread.h>
+#endif
+
+#ifdef TRACE_MALLOC
+#define malloc malloc0
+#define free free0
+void *malloc(size_t);
+void free(void *);
+#endif
+
+typedef long long p9_vlong;
+typedef unsigned long long p9_uvlong;
+typedef uintptr_t uintptr;
--- /dev/null
+++ b/libc/dofmt.c
@@ -1,0 +1,539 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/* format the output into f->to and return the number of characters fmted */
+int
+dofmt(Fmt *f, char *fmt)
+{+ Rune rune, *rt, *rs;
+ int r;
+ char *t, *s;
+ int n, nfmt;
+
+ nfmt = f->nfmt;
+ for(;;){+ if(f->runes){+ rt = (Rune*)f->to;
+ rs = (Rune*)f->stop;
+ while((r = *(uchar*)fmt) && r != '%'){+ if(r < Runeself)
+ fmt++;
+ else{+ fmt += chartorune(&rune, fmt);
+ r = rune;
+ }
+ FMTRCHAR(f, rt, rs, r);
+ }
+ fmt++;
+ f->nfmt += rt - (Rune *)f->to;
+ f->to = rt;
+ if(!r)
+ return f->nfmt - nfmt;
+ f->stop = rs;
+ }else{+ t = (char*)f->to;
+ s = (char*)f->stop;
+ while((r = *(uchar*)fmt) && r != '%'){+ if(r < Runeself){+ FMTCHAR(f, t, s, r);
+ fmt++;
+ }else{+ n = chartorune(&rune, fmt);
+ if(t + n > s){+ t = (char*)__fmtflush(f, t, n);
+ if(t != nil)
+ s = (char*)f->stop;
+ else
+ return -1;
+ }
+ while(n--)
+ *t++ = *fmt++;
+ }
+ }
+ fmt++;
+ f->nfmt += t - (char *)f->to;
+ f->to = t;
+ if(!r)
+ return f->nfmt - nfmt;
+ f->stop = s;
+ }
+
+ fmt = (char*)__fmtdispatch(f, fmt, 0);
+ if(fmt == nil)
+ return -1;
+ }
+}
+
+void *
+__fmtflush(Fmt *f, void *t, int len)
+{+ if(f->runes)
+ f->nfmt += (Rune*)t - (Rune*)f->to;
+ else
+ f->nfmt += (char*)t - (char *)f->to;
+ f->to = t;
+ if(f->flush == 0 || (*f->flush)(f) == 0 || (char*)f->to + len > (char*)f->stop){+ f->stop = f->to;
+ return nil;
+ }
+ return f->to;
+}
+
+/*
+ * put a formatted block of memory sz bytes long of n runes into the output buffer,
+ * left/right justified in a field of at least f->width charactes
+ */
+int
+__fmtpad(Fmt *f, int n)
+{+ char *t, *s;
+ int i;
+
+ t = (char*)f->to;
+ s = (char*)f->stop;
+ for(i = 0; i < n; i++)
+ FMTCHAR(f, t, s, ' ');
+ f->nfmt += t - (char *)f->to;
+ f->to = t;
+ return 0;
+}
+
+int
+__rfmtpad(Fmt *f, int n)
+{+ Rune *t, *s;
+ int i;
+
+ t = (Rune*)f->to;
+ s = (Rune*)f->stop;
+ for(i = 0; i < n; i++)
+ FMTRCHAR(f, t, s, ' ');
+ f->nfmt += t - (Rune *)f->to;
+ f->to = t;
+ return 0;
+}
+
+int
+__fmtcpy(Fmt *f, const void *vm, int n, int sz)
+{+ Rune *rt, *rs, r;
+ char *t, *s, *m, *me;
+ ulong fl;
+ int nc, w;
+
+ m = (char*)vm;
+ me = m + sz;
+ w = f->width;
+ fl = f->flags;
+ if((fl & FmtPrec) && n > f->prec)
+ n = f->prec;
+ if(f->runes){+ if(!(fl & FmtLeft) && __rfmtpad(f, w - n) < 0)
+ return -1;
+ rt = (Rune*)f->to;
+ rs = (Rune*)f->stop;
+ for(nc = n; nc > 0; nc--){+ r = *(uchar*)m;
+ if(r < Runeself)
+ m++;
+ else if((me - m) >= UTFmax || fullrune(m, me-m))
+ m += chartorune(&r, m);
+ else
+ break;
+ FMTRCHAR(f, rt, rs, r);
+ }
+ f->nfmt += rt - (Rune *)f->to;
+ f->to = rt;
+ if(fl & FmtLeft && __rfmtpad(f, w - n) < 0)
+ return -1;
+ }else{+ if(!(fl & FmtLeft) && __fmtpad(f, w - n) < 0)
+ return -1;
+ t = (char*)f->to;
+ s = (char*)f->stop;
+ for(nc = n; nc > 0; nc--){+ r = *(uchar*)m;
+ if(r < Runeself)
+ m++;
+ else if((me - m) >= UTFmax || fullrune(m, me-m))
+ m += chartorune(&r, m);
+ else
+ break;
+ FMTRUNE(f, t, s, r);
+ }
+ f->nfmt += t - (char *)f->to;
+ f->to = t;
+ if(fl & FmtLeft && __fmtpad(f, w - n) < 0)
+ return -1;
+ }
+ return 0;
+}
+
+int
+__fmtrcpy(Fmt *f, const void *vm, int n)
+{+ Rune r, *m, *me, *rt, *rs;
+ char *t, *s;
+ ulong fl;
+ int w;
+
+ m = (Rune*)vm;
+ w = f->width;
+ fl = f->flags;
+ if((fl & FmtPrec) && n > f->prec)
+ n = f->prec;
+ if(f->runes){+ if(!(fl & FmtLeft) && __rfmtpad(f, w - n) < 0)
+ return -1;
+ rt = (Rune*)f->to;
+ rs = (Rune*)f->stop;
+ for(me = m + n; m < me; m++)
+ FMTRCHAR(f, rt, rs, *m);
+ f->nfmt += rt - (Rune *)f->to;
+ f->to = rt;
+ if(fl & FmtLeft && __rfmtpad(f, w - n) < 0)
+ return -1;
+ }else{+ if(!(fl & FmtLeft) && __fmtpad(f, w - n) < 0)
+ return -1;
+ t = (char*)f->to;
+ s = (char*)f->stop;
+ for(me = m + n; m < me; m++){+ r = *m;
+ FMTRUNE(f, t, s, r);
+ }
+ f->nfmt += t - (char *)f->to;
+ f->to = t;
+ if(fl & FmtLeft && __fmtpad(f, w - n) < 0)
+ return -1;
+ }
+ return 0;
+}
+
+/* fmt out one character */
+int
+__charfmt(Fmt *f)
+{+ char x[1];
+
+ x[0] = va_arg(f->args, int);
+ f->prec = 1;
+ return __fmtcpy(f, (const char*)x, 1, 1);
+}
+
+/* fmt out one rune */
+int
+__runefmt(Fmt *f)
+{+ Rune x[1];
+
+ x[0] = va_arg(f->args, int);
+ return __fmtrcpy(f, (const void*)x, 1);
+}
+
+/* public helper routine: fmt out a null terminated string already in hand */
+int
+fmtstrcpy(Fmt *f, char *s)
+{+ int i, j;
+ Rune r;
+
+ if(!s)
+ return __fmtcpy(f, "<nil>", 5, 5);
+ /* if precision is specified, make sure we don't wander off the end */
+ if(f->flags & FmtPrec){+ i = 0;
+ for(j=0; j<f->prec && s[i]; j++)
+ i += chartorune(&r, s+i);
+ return __fmtcpy(f, s, j, i);
+ }
+ return __fmtcpy(f, s, utflen(s), strlen(s));
+}
+
+/* fmt out a null terminated utf string */
+int
+__strfmt(Fmt *f)
+{+ char *s;
+
+ s = va_arg(f->args, char *);
+ return fmtstrcpy(f, s);
+}
+
+/* public helper routine: fmt out a null terminated rune string already in hand */
+int
+fmtrunestrcpy(Fmt *f, Rune *s)
+{+ Rune *e;
+ int n, p;
+
+ if(!s)
+ return __fmtcpy(f, "<nil>", 5, 5);
+ /* if precision is specified, make sure we don't wander off the end */
+ if(f->flags & FmtPrec){+ p = f->prec;
+ for(n = 0; n < p; n++)
+ if(s[n] == 0)
+ break;
+ }else{+ for(e = s; *e; e++)
+ ;
+ n = e - s;
+ }
+ return __fmtrcpy(f, s, n);
+}
+
+/* fmt out a null terminated rune string */
+int
+__runesfmt(Fmt *f)
+{+ Rune *s;
+
+ s = va_arg(f->args, Rune *);
+ return fmtrunestrcpy(f, s);
+}
+
+/* fmt a % */
+int
+__percentfmt(Fmt *f)
+{+ Rune x[1];
+
+ x[0] = f->r;
+ f->prec = 1;
+ return __fmtrcpy(f, (const void*)x, 1);
+}
+
+/* fmt an integer */
+int
+__ifmt(Fmt *f)
+{+ char buf[70], *p, *conv;
+ uvlong vu;
+ ulong u;
+ int neg, base, i, n, fl, w, isv;
+
+ neg = 0;
+ fl = f->flags;
+ isv = 0;
+ vu = 0;
+ u = 0;
+ /*
+ * Unsigned verbs for ANSI C
+ */
+ switch(f->r){+ case 'x':
+ case 'X':
+ case 'o':
+ case 'u':
+ case 'p':
+ fl |= FmtUnsigned;
+ fl &= ~(FmtSign|FmtSpace);
+ break;
+ }
+ if(f->r == 'p'){+ if(sizeof(void*) == sizeof(uvlong)){+ isv = 1;
+ vu = (uvlong)va_arg(f->args, uvlong);
+ }else
+ u = (ulong)va_arg(f->args, ulong);
+ f->r = 'x';
+ fl |= FmtUnsigned;
+ }else if(fl & FmtVLong){+ isv = 1;
+ if(fl & FmtUnsigned)
+ vu = va_arg(f->args, uvlong);
+ else
+ vu = va_arg(f->args, vlong);
+ }else if(fl & FmtLong){+ if(fl & FmtUnsigned)
+ u = va_arg(f->args, ulong);
+ else
+ u = va_arg(f->args, long);
+ }else if(fl & FmtByte){+ if(fl & FmtUnsigned)
+ u = (uchar)va_arg(f->args, int);
+ else
+ u = (char)va_arg(f->args, int);
+ }else if(fl & FmtShort){+ if(fl & FmtUnsigned)
+ u = (ushort)va_arg(f->args, int);
+ else
+ u = (short)va_arg(f->args, int);
+ }else{+ if(fl & FmtUnsigned)
+ u = va_arg(f->args, uint);
+ else
+ u = va_arg(f->args, int);
+ }
+ conv = "0123456789abcdef";
+ switch(f->r){+ case 'd':
+ case 'i':
+ case 'u':
+ base = 10;
+ break;
+ case 'x':
+ base = 16;
+ break;
+ case 'X':
+ base = 16;
+ conv = "0123456789ABCDEF";
+ break;
+ case 'b':
+ base = 2;
+ break;
+ case 'o':
+ base = 8;
+ break;
+ default:
+ return -1;
+ }
+ if(!(fl & FmtUnsigned)){+ if(isv && (vlong)vu < 0){+ vu = -(vlong)vu;
+ neg = 1;
+ }else if(!isv && (long)u < 0){+ u = -(long)u;
+ neg = 1;
+ }
+ }
+ p = buf + sizeof buf - 1;
+ n = 0;
+ if(isv){+ while(vu){+ i = vu % base;
+ vu /= base;
+ if((fl & FmtComma) && n % 4 == 3){+ *p-- = ',';
+ n++;
+ }
+ *p-- = conv[i];
+ n++;
+ }
+ }else{+ while(u){+ i = u % base;
+ u /= base;
+ if((fl & FmtComma) && n % 4 == 3){+ *p-- = ',';
+ n++;
+ }
+ *p-- = conv[i];
+ n++;
+ }
+ }
+ if(n == 0){+ *p-- = '0';
+ n = 1;
+ }
+ for(w = f->prec; n < w && p > buf+3; n++)
+ *p-- = '0';
+ if(neg || (fl & (FmtSign|FmtSpace)))
+ n++;
+ if(fl & FmtSharp){+ if(base == 16)
+ n += 2;
+ else if(base == 8){+ if(p[1] == '0')
+ fl &= ~FmtSharp;
+ else
+ n++;
+ }
+ }
+ if((fl & FmtZero) && !(fl & (FmtLeft|FmtPrec))){+ for(w = f->width; n < w && p > buf+3; n++)
+ *p-- = '0';
+ f->width = 0;
+ }
+ if(fl & FmtSharp){+ if(base == 16)
+ *p-- = f->r;
+ if(base == 16 || base == 8)
+ *p-- = '0';
+ }
+ if(neg)
+ *p-- = '-';
+ else if(fl & FmtSign)
+ *p-- = '+';
+ else if(fl & FmtSpace)
+ *p-- = ' ';
+ f->flags &= ~FmtPrec;
+ return __fmtcpy(f, p + 1, n, n);
+}
+
+int
+__countfmt(Fmt *f)
+{+ void *p;
+ ulong fl;
+
+ fl = f->flags;
+ p = va_arg(f->args, void*);
+ if(fl & FmtVLong){+ *(vlong*)p = f->nfmt;
+ }else if(fl & FmtLong){+ *(long*)p = f->nfmt;
+ }else if(fl & FmtByte){+ *(char*)p = f->nfmt;
+ }else if(fl & FmtShort){+ *(short*)p = f->nfmt;
+ }else{+ *(int*)p = f->nfmt;
+ }
+ return 0;
+}
+
+int
+__flagfmt(Fmt *f)
+{+ switch(f->r){+ case ',':
+ f->flags |= FmtComma;
+ break;
+ case '-':
+ f->flags |= FmtLeft;
+ break;
+ case '+':
+ f->flags |= FmtSign;
+ break;
+ case '#':
+ f->flags |= FmtSharp;
+ break;
+ case ' ':
+ f->flags |= FmtSpace;
+ break;
+ case 'u':
+ f->flags |= FmtUnsigned;
+ break;
+ case 'h':
+ if(f->flags & FmtShort)
+ f->flags |= FmtByte;
+ f->flags |= FmtShort;
+ break;
+ case 'L':
+ f->flags |= FmtLDouble;
+ break;
+ case 'l':
+ if(f->flags & FmtLong)
+ f->flags |= FmtVLong;
+ f->flags |= FmtLong;
+ break;
+ }
+ return 1;
+}
+
+/* default error format */
+int
+__badfmt(Fmt *f)
+{+ char x[3];
+
+ x[0] = '%';
+ x[1] = f->r;
+ x[2] = '%';
+ f->prec = 3;
+ __fmtcpy(f, (const void*)x, 3, 3);
+ return 0;
+}
--- /dev/null
+++ b/libc/dorfmt.c
@@ -1,0 +1,46 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/* format the output into f->to and return the number of characters fmted */
+
+int
+dorfmt(Fmt *f, const Rune *fmt)
+{+ Rune *rt, *rs;
+ int r;
+ char *t, *s;
+ int nfmt;
+
+ nfmt = f->nfmt;
+ for(;;){+ if(f->runes){+ rt = f->to;
+ rs = f->stop;
+ while((r = *fmt++) && r != '%'){+ FMTRCHAR(f, rt, rs, r);
+ }
+ f->nfmt += rt - (Rune *)f->to;
+ f->to = rt;
+ if(!r)
+ return f->nfmt - nfmt;
+ f->stop = rs;
+ }else{+ t = f->to;
+ s = f->stop;
+ while((r = *fmt++) && r != '%'){+ FMTRUNE(f, t, f->stop, r);
+ }
+ f->nfmt += t - (char *)f->to;
+ f->to = t;
+ if(!r)
+ return f->nfmt - nfmt;
+ f->stop = s;
+ }
+
+ fmt = __fmtdispatch(f, (Rune*)fmt, 1);
+ if(fmt == nil)
+ return -1;
+ }
+ return 0; /* not reached */
+}
--- /dev/null
+++ b/libc/encodefmt.c
@@ -1,0 +1,78 @@
+#include <u.h>
+#include <libc.h>
+#include <ctype.h>
+
+int
+encodefmt(Fmt *f)
+{+ char *out;
+ char *buf;
+ int len;
+ int ilen;
+ int rv;
+ uchar *b;
+ char *p;
+ char obuf[64]; // rsc optimization
+
+ if(!(f->flags&FmtPrec) || f->prec < 1)
+ goto error;
+
+ b = va_arg(f->args, uchar*);
+ if(b == 0)
+ return fmtstrcpy(f, "<nil>");
+
+ ilen = f->prec;
+ f->prec = 0;
+ f->flags &= ~FmtPrec;
+ switch(f->r){+ case '<':
+ len = (8*ilen+4)/5 + 3;
+ break;
+ case '[':
+ len = (8*ilen+5)/6 + 4;
+ break;
+ case 'H':
+ len = 2*ilen + 1;
+ break;
+ default:
+ goto error;
+ }
+
+ if(len > sizeof(obuf)){+ buf = malloc(len);
+ if(buf == nil)
+ goto error;
+ } else
+ buf = obuf;
+
+ // convert
+ out = buf;
+ switch(f->r){+ case '[':
+ rv = enc64(out, len, b, ilen);
+ break;
+ case '<':
+ rv = enc32(out, len, b, ilen);
+ break;
+ case 'H':
+ rv = enc16(out, len, b, ilen);
+ break;
+ default:
+ rv = -1;
+ break;
+ }
+ if(rv < 0)
+ goto error;
+
+ if((f->flags & FmtLong) != 0 && f->r != '[')
+ for(p = buf; *p; p++)
+ *p = tolower(*p);
+
+ fmtstrcpy(f, buf);
+ if(buf != obuf)
+ free(buf);
+ return 0;
+
+error:
+ return fmtstrcpy(f, "<encodefmt>");
+}
--- /dev/null
+++ b/libc/fltfmt.c
@@ -1,0 +1,375 @@
+#include <u.h>
+#include <libc.h>
+#include <float.h>
+#include <ctype.h>
+#include "fmtdef.h"
+
+enum
+{+ FDIGIT = 30,
+ FDEFLT = 6,
+ NSIGNIF = 17
+};
+
+/*
+ * first few powers of 10, enough for about 1/2 of the
+ * total space for doubles.
+ */
+static double pows10[] =
+{+ 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
+ 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
+ 1e20, 1e21, 1e22, 1e23, 1e24, 1e25, 1e26, 1e27, 1e28, 1e29,
+ 1e30, 1e31, 1e32, 1e33, 1e34, 1e35, 1e36, 1e37, 1e38, 1e39,
+ 1e40, 1e41, 1e42, 1e43, 1e44, 1e45, 1e46, 1e47, 1e48, 1e49,
+ 1e50, 1e51, 1e52, 1e53, 1e54, 1e55, 1e56, 1e57, 1e58, 1e59,
+ 1e60, 1e61, 1e62, 1e63, 1e64, 1e65, 1e66, 1e67, 1e68, 1e69,
+ 1e70, 1e71, 1e72, 1e73, 1e74, 1e75, 1e76, 1e77, 1e78, 1e79,
+ 1e80, 1e81, 1e82, 1e83, 1e84, 1e85, 1e86, 1e87, 1e88, 1e89,
+ 1e90, 1e91, 1e92, 1e93, 1e94, 1e95, 1e96, 1e97, 1e98, 1e99,
+ 1e100, 1e101, 1e102, 1e103, 1e104, 1e105, 1e106, 1e107, 1e108, 1e109,
+ 1e110, 1e111, 1e112, 1e113, 1e114, 1e115, 1e116, 1e117, 1e118, 1e119,
+ 1e120, 1e121, 1e122, 1e123, 1e124, 1e125, 1e126, 1e127, 1e128, 1e129,
+ 1e130, 1e131, 1e132, 1e133, 1e134, 1e135, 1e136, 1e137, 1e138, 1e139,
+ 1e140, 1e141, 1e142, 1e143, 1e144, 1e145, 1e146, 1e147, 1e148, 1e149,
+ 1e150, 1e151, 1e152, 1e153, 1e154, 1e155, 1e156, 1e157, 1e158, 1e159,
+};
+
+#undef pow10
+#define pow10(x) fmtpow10(x)
+
+static double
+pow10(int n)
+{+ double d;
+ int neg;
+
+ neg = 0;
+ if(n < 0){+ if(n < DBL_MIN_10_EXP){+ return 0.;
+ }
+ neg = 1;
+ n = -n;
+ }else if(n > DBL_MAX_10_EXP){+ return HUGE_VAL;
+ }
+ if(n < (int)(sizeof(pows10)/sizeof(pows10[0])))
+ d = pows10[n];
+ else{+ d = pows10[sizeof(pows10)/sizeof(pows10[0]) - 1];
+ for(;;){+ n -= sizeof(pows10)/sizeof(pows10[0]) - 1;
+ if(n < (int)(sizeof(pows10)/sizeof(pows10[0]))){+ d *= pows10[n];
+ break;
+ }
+ d *= pows10[sizeof(pows10)/sizeof(pows10[0]) - 1];
+ }
+ }
+ if(neg){+ return 1./d;
+ }
+ return d;
+}
+
+static int
+xadd(char *a, int n, int v)
+{+ char *b;
+ int c;
+
+ if(n < 0 || n >= NSIGNIF)
+ return 0;
+ for(b = a+n; b >= a; b--) {+ c = *b + v;
+ if(c <= '9') {+ *b = c;
+ return 0;
+ }
+ *b = '0';
+ v = 1;
+ }
+ *a = '1'; /* overflow adding */
+ return 1;
+}
+
+static int
+xsub(char *a, int n, int v)
+{+ char *b;
+ int c;
+
+ for(b = a+n; b >= a; b--) {+ c = *b - v;
+ if(c >= '0') {+ *b = c;
+ return 0;
+ }
+ *b = '9';
+ v = 1;
+ }
+ *a = '9'; /* underflow subtracting */
+ return 1;
+}
+
+static void
+xdtoa(Fmt *fmt, char *s2, double f)
+{+ char s1[NSIGNIF+10];
+ double g, h;
+ int e, d, i, n;
+ int c1, c2, c3, c4, ucase, sign, chr, prec;
+
+ prec = FDEFLT;
+ if(fmt->flags & FmtPrec)
+ prec = fmt->prec;
+ if(prec > FDIGIT)
+ prec = FDIGIT;
+ if(__isNaN(f)) {+ strcpy(s2, "NaN");
+ return;
+ }
+ if(__isInf(f, 1)) {+ strcpy(s2, "+Inf");
+ return;
+ }
+ if(__isInf(f, -1)) {+ strcpy(s2, "-Inf");
+ return;
+ }
+ sign = 0;
+ if(f < 0) {+ f = -f;
+ sign++;
+ }
+ ucase = 0;
+ chr = fmt->r;
+ if(isupper(chr)) {+ ucase = 1;
+ chr = tolower(chr);
+ }
+
+ e = 0;
+ g = f;
+ if(g != 0) {+ frexp(f, &e);
+ e = e * .301029995664;
+ if(e >= -150 && e <= +150) {+ d = 0;
+ h = f;
+ } else {+ d = e/2;
+ h = f * pow10(-d);
+ }
+ g = h * pow10(d-e);
+ while(g < 1) {+ e--;
+ g = h * pow10(d-e);
+ }
+ while(g >= 10) {+ e++;
+ g = h * pow10(d-e);
+ }
+ }
+
+ /*
+ * convert NSIGNIF digits and convert
+ * back to get accuracy.
+ */
+ for(i=0; i<NSIGNIF; i++) {+ d = g;
+ s1[i] = d + '0';
+ g = (g - d) * 10;
+ }
+ s1[i] = 0;
+
+ /*
+ * try decimal rounding to eliminate 9s
+ */
+ c2 = prec + 1;
+ if(chr == 'f')
+ c2 += e;
+ if(c2 >= NSIGNIF-2) {+ strcpy(s2, s1);
+ d = e;
+ s1[NSIGNIF-2] = '0';
+ s1[NSIGNIF-1] = '0';
+ sprint(s1+NSIGNIF, "e%d", e-NSIGNIF+1);
+ g = strtod(s1, nil);
+ if(g == f)
+ goto found;
+ if(xadd(s1, NSIGNIF-3, 1)) {+ e++;
+ sprint(s1+NSIGNIF, "e%d", e-NSIGNIF+1);
+ }
+ g = strtod(s1, nil);
+ if(g == f)
+ goto found;
+ strcpy(s1, s2);
+ e = d;
+ }
+
+ /*
+ * convert back so s1 gets exact answer
+ */
+ for(;;) {+ sprint(s1+NSIGNIF, "e%d", e-NSIGNIF+1);
+ g = strtod(s1, nil);
+ if(f > g) {+ if(xadd(s1, NSIGNIF-1, 1))
+ e--;
+ continue;
+ }
+ if(f < g) {+ if(xsub(s1, NSIGNIF-1, 1))
+ e++;
+ continue;
+ }
+ break;
+ }
+
+found:
+ /*
+ * sign
+ */
+ d = 0;
+ i = 0;
+ if(sign)
+ s2[d++] = '-';
+ else if(fmt->flags & FmtSign)
+ s2[d++] = '+';
+ else if(fmt->flags & FmtSpace)
+ s2[d++] = ' ';
+
+ /*
+ * copy into final place
+ * c1 digits of leading '0'
+ * c2 digits from conversion
+ * c3 digits of trailing '0'
+ * c4 digits after '.'
+ */
+ c1 = 0;
+ c2 = prec + 1;
+ c3 = 0;
+ c4 = prec;
+ switch(chr) {+ default:
+ if(xadd(s1, c2, 5))
+ e++;
+ break;
+ case 'g':
+ /*
+ * decide on 'e' of 'f' style convers
+ */
+ if(xadd(s1, c2, 5))
+ e++;
+ if(e >= -5 && e <= prec) {+ c1 = -e - 1;
+ c4 = prec - e;
+ chr = 'h'; // flag for 'f' style
+ }
+ break;
+ case 'f':
+ if(xadd(s1, c2+e, 5))
+ e++;
+ c1 = -e;
+ if(c1 > prec)
+ c1 = c2;
+ c2 += e;
+ break;
+ }
+
+ /*
+ * clean up c1 c2 and c3
+ */
+ if(c1 < 0)
+ c1 = 0;
+ if(c2 < 0)
+ c2 = 0;
+ if(c2 > NSIGNIF) {+ c3 = c2-NSIGNIF;
+ c2 = NSIGNIF;
+ }
+
+ /*
+ * copy digits
+ */
+ while(c1 > 0) {+ if(c1+c2+c3 == c4)
+ s2[d++] = '.';
+ s2[d++] = '0';
+ c1--;
+ }
+ while(c2 > 0) {+ if(c2+c3 == c4)
+ s2[d++] = '.';
+ s2[d++] = s1[i++];
+ c2--;
+ }
+ while(c3 > 0) {+ if(c3 == c4)
+ s2[d++] = '.';
+ s2[d++] = '0';
+ c3--;
+ }
+
+ /*
+ * strip trailing '0' on g conv
+ */
+ if(fmt->flags & FmtSharp) {+ if(0 == c4)
+ s2[d++] = '.';
+ } else
+ if(chr == 'g' || chr == 'h') {+ for(n=d-1; n>=0; n--)
+ if(s2[n] != '0')
+ break;
+ for(i=n; i>=0; i--)
+ if(s2[i] == '.') {+ d = n;
+ if(i != n)
+ d++;
+ break;
+ }
+ }
+ if(chr == 'e' || chr == 'g') {+ if(ucase)
+ s2[d++] = 'E';
+ else
+ s2[d++] = 'e';
+ c1 = e;
+ if(c1 < 0) {+ s2[d++] = '-';
+ c1 = -c1;
+ } else
+ s2[d++] = '+';
+ if(c1 >= 100) {+ s2[d++] = c1/100 + '0';
+ c1 = c1%100;
+ }
+ s2[d++] = c1/10 + '0';
+ s2[d++] = c1%10 + '0';
+ }
+ s2[d] = 0;
+}
+
+static int
+floatfmt(Fmt *fmt, double f)
+{+ char s[341]; /* precision+exponent+sign+'.'+null */
+
+ xdtoa(fmt, s, f);
+ fmt->flags &= FmtWidth|FmtLeft;
+ __fmtcpy(fmt, s, strlen(s), strlen(s));
+ return 0;
+}
+
+int
+__efgfmt(Fmt *f)
+{+ double d;
+
+ d = va_arg(f->args, double);
+ return floatfmt(f, d);
+}
--- /dev/null
+++ b/libc/fmt.c
@@ -1,0 +1,216 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+enum
+{+ Maxfmt = 64
+};
+
+typedef struct Convfmt Convfmt;
+struct Convfmt
+{+ int c;
+ volatile Fmts fmt; /* for spin lock in fmtfmt; avoids race due to write order */
+};
+
+struct
+{+ /* lock by calling __fmtlock, __fmtunlock */
+ int nfmt;
+ Convfmt fmt[Maxfmt];
+} fmtalloc;
+
+static Convfmt knownfmt[] = {+ ' ', __flagfmt,
+ '#', __flagfmt,
+ '%', __percentfmt,
+ '+', __flagfmt,
+ ',', __flagfmt,
+ '-', __flagfmt,
+ 'C', __runefmt, /* Plan 9 addition */
+ 'E', __efgfmt,
+#ifndef PLAN9PORT
+ 'F', __efgfmt, /* ANSI only */
+#endif
+ 'G', __efgfmt,
+#ifndef PLAN9PORT
+ 'L', __flagfmt, /* ANSI only */
+#endif
+ 'S', __runesfmt, /* Plan 9 addition */
+ 'X', __ifmt,
+ 'b', __ifmt, /* Plan 9 addition */
+ 'c', __charfmt,
+ 'd', __ifmt,
+ 'e', __efgfmt,
+ 'f', __efgfmt,
+ 'g', __efgfmt,
+ 'h', __flagfmt,
+#ifndef PLAN9PORT
+ 'i', __ifmt, /* ANSI only */
+#endif
+ 'l', __flagfmt,
+ 'n', __countfmt,
+ 'o', __ifmt,
+ 'p', __ifmt,
+// 'r', __errfmt,
+ 's', __strfmt,
+#ifdef PLAN9PORT
+ 'u', __flagfmt,
+#else
+ 'u', __ifmt,
+#endif
+ 'x', __ifmt,
+ 0, 0,
+};
+
+
+int (*fmtdoquote)(int);
+
+/*
+ * __fmtlock() must be set
+ */
+static int
+__fmtinstall(int c, Fmts f)
+{+ Convfmt *p, *ep;
+
+ if(c<=0 || c>=65536)
+ return -1;
+ if(!f)
+ f = __badfmt;
+
+ ep = &fmtalloc.fmt[fmtalloc.nfmt];
+ for(p=fmtalloc.fmt; p<ep; p++)
+ if(p->c == c)
+ break;
+
+ if(p == &fmtalloc.fmt[Maxfmt])
+ return -1;
+
+ p->fmt = f;
+ if(p == ep){ /* installing a new format character */+ fmtalloc.nfmt++;
+ p->c = c;
+ }
+
+ return 0;
+}
+
+int
+fmtinstall(int c, int (*f)(Fmt*))
+{+ int ret;
+
+ __fmtlock();
+ ret = __fmtinstall(c, f);
+ __fmtunlock();
+ return ret;
+}
+
+static Fmts
+fmtfmt(int c)
+{+ Convfmt *p, *ep;
+
+ ep = &fmtalloc.fmt[fmtalloc.nfmt];
+ for(p=fmtalloc.fmt; p<ep; p++)
+ if(p->c == c){+ while(p->fmt == 0) /* loop until value is updated */
+ ;
+ return p->fmt;
+ }
+
+ /* is this a predefined format char? */
+ __fmtlock();
+ for(p=knownfmt; p->c; p++)
+ if(p->c == c){+ __fmtinstall(p->c, p->fmt);
+ __fmtunlock();
+ return p->fmt;
+ }
+ __fmtunlock();
+
+ return __badfmt;
+}
+
+void*
+__fmtdispatch(Fmt *f, void *fmt, int isrunes)
+{+ Rune rune, r;
+ int i, n;
+
+ f->flags = 0;
+ f->width = f->prec = 0;
+
+ for(;;){+ if(isrunes){+ r = *(Rune*)fmt;
+ fmt = (Rune*)fmt + 1;
+ }else{+ fmt = (char*)fmt + chartorune(&rune, (char*)fmt);
+ r = rune;
+ }
+ f->r = r;
+ switch(r){+ case '\0':
+ return nil;
+ case '.':
+ f->flags |= FmtWidth|FmtPrec;
+ continue;
+ case '0':
+ if(!(f->flags & FmtWidth)){+ f->flags |= FmtZero;
+ continue;
+ }
+ /* fall through */
+ case '1': case '2': case '3': case '4':
+ case '5': case '6': case '7': case '8': case '9':
+ i = 0;
+ while(r >= '0' && r <= '9'){+ i = i * 10 + r - '0';
+ if(isrunes){+ r = *(Rune*)fmt;
+ fmt = (Rune*)fmt + 1;
+ }else{+ r = *(char*)fmt;
+ fmt = (char*)fmt + 1;
+ }
+ }
+ if(isrunes)
+ fmt = (Rune*)fmt - 1;
+ else
+ fmt = (char*)fmt - 1;
+ numflag:
+ if(f->flags & FmtWidth){+ f->flags |= FmtPrec;
+ f->prec = i;
+ }else{+ f->flags |= FmtWidth;
+ f->width = i;
+ }
+ continue;
+ case '*':
+ i = va_arg(f->args, int);
+ if(i < 0){+ /*
+ * negative precision =>
+ * ignore the precision.
+ */
+ if(f->flags & FmtPrec){+ f->flags &= ~FmtPrec;
+ f->prec = 0;
+ continue;
+ }
+ i = -i;
+ f->flags |= FmtLeft;
+ }
+ goto numflag;
+ }
+ n = (*fmtfmt(r))(f);
+ if(n < 0)
+ return nil;
+ if(n == 0)
+ return fmt;
+ }
+}
--- /dev/null
+++ b/libc/fmtdef.h
@@ -1,0 +1,103 @@
+/*
+ * dofmt -- format to a buffer
+ * the number of characters formatted is returned,
+ * or -1 if there was an error.
+ * if the buffer is ever filled, flush is called.
+ * it should reset the buffer and return whether formatting should continue.
+ */
+
+typedef int (*Fmts)(Fmt*);
+
+typedef struct Quoteinfo Quoteinfo;
+struct Quoteinfo
+{+ int quoted; /* if set, string must be quoted */
+ int nrunesin; /* number of input runes that can be accepted */
+ int nbytesin; /* number of input bytes that can be accepted */
+ int nrunesout; /* number of runes that will be generated */
+ int nbytesout; /* number of bytes that will be generated */
+};
+
+/* Edit .+1,/^$/ |cfn |grep -v static | grep __ */
+double __Inf(int sign);
+double __NaN(void);
+int __badfmt(Fmt *f);
+int __charfmt(Fmt *f);
+int __countfmt(Fmt *f);
+int __efgfmt(Fmt *fmt);
+int __errfmt(Fmt *f);
+int __flagfmt(Fmt *f);
+int __fmtFdFlush(Fmt *f);
+int __fmtcpy(Fmt *f, const void *vm, int n, int sz);
+void* __fmtdispatch(Fmt *f, void *fmt, int isrunes);
+void * __fmtflush(Fmt *f, void *t, int len);
+void __fmtlock(void);
+int __fmtpad(Fmt *f, int n);
+double __fmtpow10(int n);
+int __fmtrcpy(Fmt *f, const void *vm, int n);
+void __fmtunlock(void);
+int __ifmt(Fmt *f);
+int __isInf(double d, int sign);
+int __isNaN(double d);
+int __needsquotes(char *s, int *quotelenp);
+int __percentfmt(Fmt *f);
+void __quotesetup(char *s, Rune *r, int nin, int nout, Quoteinfo *q, int sharp, int runesout);
+int __quotestrfmt(int runesin, Fmt *f);
+int __rfmtpad(Fmt *f, int n);
+int __runefmt(Fmt *f);
+int __runeneedsquotes(Rune *r, int *quotelenp);
+int __runesfmt(Fmt *f);
+int __strfmt(Fmt *f);
+
+#define FMTCHAR(f, t, s, c)\
+ do{\+ if(t + 1 > (char*)s){\+ t = __fmtflush(f, t, 1);\
+ if(t != nil)\
+ s = f->stop;\
+ else\
+ return -1;\
+ }\
+ *t++ = c;\
+ }while(0)
+
+#define FMTRCHAR(f, t, s, c)\
+ do{\+ if(t + 1 > (Rune*)s){\+ t = __fmtflush(f, t, sizeof(Rune));\
+ if(t != nil)\
+ s = f->stop;\
+ else\
+ return -1;\
+ }\
+ *t++ = c;\
+ }while(0)
+
+#define FMTRUNE(f, t, s, r)\
+ do{\+ Rune _rune;\
+ int _runelen;\
+ if(t + UTFmax > (char*)s && t + (_runelen = runelen(r)) > (char*)s){\+ t = __fmtflush(f, t, _runelen);\
+ if(t != nil)\
+ s = f->stop;\
+ else\
+ return -1;\
+ }\
+ if(r < Runeself)\
+ *t++ = r;\
+ else{\+ _rune = r;\
+ t += runetochar(t, &_rune);\
+ }\
+ }while(0)
+
+#ifdef va_copy
+# define VA_COPY(a,b) va_copy(a,b)
+# define VA_END(a) va_end(a)
+#else
+# define VA_COPY(a,b) (a) = (b)
+# define VA_END(a)
+#endif
+
+#define PLAN9PORT
--- /dev/null
+++ b/libc/fmtfd.c
@@ -1,0 +1,32 @@
+#include <inttypes.h>
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/*
+ * public routine for final flush of a formatting buffer
+ * to a file descriptor; returns total char count.
+ */
+int
+fmtfdflush(Fmt *f)
+{+ if(__fmtFdFlush(f) <= 0)
+ return -1;
+ return f->nfmt;
+}
+
+/*
+ * initialize an output buffer for buffered printing
+ */
+int
+fmtfdinit(Fmt *f, int fd, char *buf, int size)
+{+ f->runes = 0;
+ f->start = buf;
+ f->to = buf;
+ f->stop = buf + size;
+ f->flush = __fmtFdFlush;
+ f->farg = (void*)(uintptr_t)fd;
+ f->nfmt = 0;
+ return 0;
+}
--- /dev/null
+++ b/libc/fmtfdflush.c
@@ -1,0 +1,20 @@
+#include <inttypes.h>
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/*
+ * generic routine for flushing a formatting buffer
+ * to a file descriptor
+ */
+int
+__fmtFdFlush(Fmt *f)
+{+ int n;
+
+ n = (char*)f->to - (char*)f->start;
+ if(n && write((uintptr_t)f->farg, f->start, n) != n)
+ return 0;
+ f->to = f->start;
+ return 1;
+}
--- /dev/null
+++ b/libc/fmtlock.c
@@ -1,0 +1,16 @@
+#include <u.h>
+#include <libc.h>
+
+static Lock fmtl;
+
+void
+__fmtlock(void)
+{+ lock(&fmtl);
+}
+
+void
+__fmtunlock(void)
+{+ unlock(&fmtl);
+}
--- /dev/null
+++ b/libc/fmtprint.c
@@ -1,0 +1,33 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/*
+ * format a string into the output buffer
+ * designed for formats which themselves call fmt,
+ * but ignore any width flags
+ */
+int
+fmtprint(Fmt *f, char *fmt, ...)
+{+ va_list va;
+ int n;
+
+ f->flags = 0;
+ f->width = 0;
+ f->prec = 0;
+ VA_COPY(va, f->args);
+ VA_END(f->args);
+ va_start(f->args, fmt);
+ n = dofmt(f, fmt);
+ va_end(f->args);
+ f->flags = 0;
+ f->width = 0;
+ f->prec = 0;
+ VA_COPY(f->args,va);
+ VA_END(va);
+ if(n >= 0)
+ return 0;
+ return n;
+}
+
--- /dev/null
+++ b/libc/fmtquote.c
@@ -1,0 +1,249 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/*
+ * How many bytes of output UTF will be produced by quoting (if necessary) this string?
+ * How many runes? How much of the input will be consumed?
+ * The parameter q is filled in by __quotesetup.
+ * The string may be UTF or Runes (s or r).
+ * Return count does not include NUL.
+ * Terminate the scan at the first of:
+ * NUL in input
+ * count exceeded in input
+ * count exceeded on output
+ * *ninp is set to number of input bytes accepted.
+ * nin may be <0 initially, to avoid checking input by count.
+ */
+void
+__quotesetup(char *s, Rune *r, int nin, int nout, Quoteinfo *q, int sharp, int runesout)
+{+ int w;
+ Rune c;
+
+ q->quoted = 0;
+ q->nbytesout = 0;
+ q->nrunesout = 0;
+ q->nbytesin = 0;
+ q->nrunesin = 0;
+ if(sharp || nin==0 || (s && *s=='\0') || (r && *r=='\0')){+ if(nout < 2)
+ return;
+ q->quoted = 1;
+ q->nbytesout = 2;
+ q->nrunesout = 2;
+ }
+ for(; nin!=0; nin--){+ if(s)
+ w = chartorune(&c, s);
+ else{+ c = *r;
+ w = runelen(c);
+ }
+
+ if(c == '\0')
+ break;
+ if(runesout){+ if(q->nrunesout+1 > nout)
+ break;
+ }else{+ if(q->nbytesout+w > nout)
+ break;
+ }
+
+ if((c <= L' ') || (c == L'\'') || (fmtdoquote!=0 && fmtdoquote(c))){+ if(!q->quoted){+ if(runesout){+ if(1+q->nrunesout+1+1 > nout) /* no room for quotes */
+ break;
+ }else{+ if(1+q->nbytesout+w+1 > nout) /* no room for quotes */
+ break;
+ }
+ q->nrunesout += 2; /* include quotes */
+ q->nbytesout += 2; /* include quotes */
+ q->quoted = 1;
+ }
+ if(c == '\'') {+ if(runesout){+ if(1+q->nrunesout+1 > nout) /* no room for quotes */
+ break;
+ }else{+ if(1+q->nbytesout+w > nout) /* no room for quotes */
+ break;
+ }
+ q->nbytesout++;
+ q->nrunesout++; /* quotes reproduce as two characters */
+ }
+ }
+
+ /* advance input */
+ if(s)
+ s += w;
+ else
+ r++;
+ q->nbytesin += w;
+ q->nrunesin++;
+
+ /* advance output */
+ q->nbytesout += w;
+ q->nrunesout++;
+ }
+}
+
+static int
+qstrfmt(char *sin, Rune *rin, Quoteinfo *q, Fmt *f)
+{+ Rune r, *rm, *rme;
+ char *t, *s, *m, *me;
+ Rune *rt, *rs;
+ ulong fl;
+ int nc, w;
+
+ m = sin;
+ me = m + q->nbytesin;
+ rm = rin;
+ rme = rm + q->nrunesin;
+
+ w = f->width;
+ fl = f->flags;
+ if(f->runes){+ if(!(fl & FmtLeft) && __rfmtpad(f, w - q->nrunesout) < 0)
+ return -1;
+ }else{+ if(!(fl & FmtLeft) && __fmtpad(f, w - q->nbytesout) < 0)
+ return -1;
+ }
+ t = (char*)f->to;
+ s = (char*)f->stop;
+ rt = (Rune*)f->to;
+ rs = (Rune*)f->stop;
+ if(f->runes)
+ FMTRCHAR(f, rt, rs, '\'');
+ else
+ FMTRUNE(f, t, s, '\'');
+ for(nc = q->nrunesin; nc > 0; nc--){+ if(sin){+ r = *(uchar*)m;
+ if(r < Runeself)
+ m++;
+ else if((me - m) >= UTFmax || fullrune(m, me-m))
+ m += chartorune(&r, m);
+ else
+ break;
+ }else{+ if(rm >= rme)
+ break;
+ r = *(uchar*)rm++;
+ }
+ if(f->runes){+ FMTRCHAR(f, rt, rs, r);
+ if(r == '\'')
+ FMTRCHAR(f, rt, rs, r);
+ }else{+ FMTRUNE(f, t, s, r);
+ if(r == '\'')
+ FMTRUNE(f, t, s, r);
+ }
+ }
+
+ if(f->runes){+ FMTRCHAR(f, rt, rs, '\'');
+ USED(rs);
+ f->nfmt += rt - (Rune *)f->to;
+ f->to = rt;
+ if(fl & FmtLeft && __rfmtpad(f, w - q->nrunesout) < 0)
+ return -1;
+ }else{+ FMTRUNE(f, t, s, '\'');
+ USED(s);
+ f->nfmt += t - (char *)f->to;
+ f->to = t;
+ if(fl & FmtLeft && __fmtpad(f, w - q->nbytesout) < 0)
+ return -1;
+ }
+ return 0;
+}
+
+int
+__quotestrfmt(int runesin, Fmt *f)
+{+ int nin, outlen;
+ Rune *r;
+ char *s;
+ Quoteinfo q;
+
+ nin = -1;
+ if(f->flags&FmtPrec)
+ nin = f->prec;
+ if(runesin){+ r = va_arg(f->args, Rune *);
+ s = nil;
+ }else{+ s = va_arg(f->args, char *);
+ r = nil;
+ }
+ if(!s && !r)
+ return __fmtcpy(f, (void*)"<nil>", 5, 5);
+
+ if(f->flush)
+ outlen = 0x7FFFFFFF; /* if we can flush, no output limit */
+ else if(f->runes)
+ outlen = (Rune*)f->stop - (Rune*)f->to;
+ else
+ outlen = (char*)f->stop - (char*)f->to;
+
+ __quotesetup(s, r, nin, outlen, &q, f->flags&FmtSharp, f->runes);
+//print("bytes in %d bytes out %d runes in %d runesout %d\n", q.nbytesin, q.nbytesout, q.nrunesin, q.nrunesout);+
+ if(runesin){+ if(!q.quoted)
+ return __fmtrcpy(f, r, q.nrunesin);
+ return qstrfmt(nil, r, &q, f);
+ }
+
+ if(!q.quoted)
+ return __fmtcpy(f, s, q.nrunesin, q.nbytesin);
+ return qstrfmt(s, nil, &q, f);
+}
+
+int
+quotestrfmt(Fmt *f)
+{+ return __quotestrfmt(0, f);
+}
+
+int
+quoterunestrfmt(Fmt *f)
+{+ return __quotestrfmt(1, f);
+}
+
+void
+quotefmtinstall(void)
+{+ fmtinstall('q', quotestrfmt);+ fmtinstall('Q', quoterunestrfmt);+}
+
+int
+__needsquotes(char *s, int *quotelenp)
+{+ Quoteinfo q;
+
+ __quotesetup(s, nil, -1, 0x7FFFFFFF, &q, 0, 0);
+ *quotelenp = q.nbytesout;
+
+ return q.quoted;
+}
+
+int
+__runeneedsquotes(Rune *r, int *quotelenp)
+{+ Quoteinfo q;
+
+ __quotesetup(nil, r, -1, 0x7FFFFFFF, &q, 0, 0);
+ *quotelenp = q.nrunesout;
+
+ return q.quoted;
+}
--- /dev/null
+++ b/libc/fmtrune.c
@@ -1,0 +1,25 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+fmtrune(Fmt *f, int r)
+{+ Rune *rt;
+ char *t;
+ int n;
+
+ if(f->runes){+ rt = (Rune*)f->to;
+ FMTRCHAR(f, rt, f->stop, r);
+ f->to = rt;
+ n = 1;
+ }else{+ t = (char*)f->to;
+ FMTRUNE(f, t, f->stop, r);
+ n = t - (char*)f->to;
+ f->to = t;
+ }
+ f->nfmt += n;
+ return 0;
+}
--- /dev/null
+++ b/libc/fmtstr.c
@@ -1,0 +1,12 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+char*
+fmtstrflush(Fmt *f)
+{+ if(f->start == nil)
+ return nil;
+ *(char*)f->to = '\0';
+ return (char*)f->start;
+}
--- /dev/null
+++ b/libc/fmtvprint.c
@@ -1,0 +1,34 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+
+/*
+ * format a string into the output buffer
+ * designed for formats which themselves call fmt,
+ * but ignore any width flags
+ */
+int
+fmtvprint(Fmt *f, char *fmt, va_list args)
+{+ va_list va;
+ int n;
+
+ f->flags = 0;
+ f->width = 0;
+ f->prec = 0;
+ VA_COPY(va,f->args);
+ VA_END(f->args);
+ VA_COPY(f->args,args);
+ n = dofmt(f, fmt);
+ f->flags = 0;
+ f->width = 0;
+ f->prec = 0;
+ VA_END(f->args);
+ VA_COPY(f->args,va);
+ VA_END(va);
+ if(n >= 0)
+ return 0;
+ return n;
+}
+
--- /dev/null
+++ b/libc/fprint.c
@@ -1,0 +1,15 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+fprint(int fd, char *fmt, ...)
+{+ int n;
+ va_list args;
+
+ va_start(args, fmt);
+ n = vfprint(fd, fmt, args);
+ va_end(args);
+ return n;
+}
--- /dev/null
+++ b/libc/genrandom.c
@@ -1,0 +1,12 @@
+#include <u.h>
+#include <libc.h>
+
+#undef long
+#undef ulong
+#include <unistd.h>
+
+void
+genrandom(uchar *buf, int nbytes)
+{+ getentropy(buf, nbytes);
+}
--- /dev/null
+++ b/libc/mallocz.c
@@ -1,0 +1,13 @@
+#include <u.h>
+#include <libc.h>
+
+void*
+mallocz(ulong n, int clr)
+{+ void *v;
+
+ v = malloc(n);
+ if(v && clr)
+ memset(v, 0, n);
+ return v;
+}
--- /dev/null
+++ b/libc/nan.h
@@ -1,0 +1,4 @@
+extern double __NaN(void);
+extern double __Inf(int);
+extern int __isNaN(double);
+extern int __isInf(double, int);
--- /dev/null
+++ b/libc/nan64.c
@@ -1,0 +1,67 @@
+/*
+ * 64-bit IEEE not-a-number routines.
+ * This is big/little-endian portable assuming that
+ * the 64-bit doubles and 64-bit integers have the
+ * same byte ordering.
+ */
+
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+#if defined (__APPLE__) || (__powerpc__)
+#define _NEEDLL
+#endif
+
+static uvlong uvnan = ((uvlong)0x7FF00000<<32)|0x00000001;
+static uvlong uvinf = ((uvlong)0x7FF00000<<32)|0x00000000;
+static uvlong uvneginf = ((uvlong)0xFFF00000<<32)|0x00000000;
+
+double
+__NaN(void)
+{+ uvlong *p;
+
+ /* gcc complains about "return *(double*)&uvnan;" */
+ p = &uvnan;
+ return *(double*)p;
+}
+
+int
+__isNaN(double d)
+{+ uvlong x;
+ double *p;
+
+ p = &d;
+ x = *(uvlong*)p;
+ return (ulong)(x>>32)==0x7FF00000 && !__isInf(d, 0);
+}
+
+double
+__Inf(int sign)
+{+ uvlong *p;
+
+ if(sign < 0)
+ p = &uvinf;
+ else
+ p = &uvneginf;
+ return *(double*)p;
+}
+
+int
+__isInf(double d, int sign)
+{+ uvlong x;
+ double *p;
+
+ p = &d;
+ x = *(uvlong*)p;
+ if(sign == 0)
+ return x==uvinf || x==uvneginf;
+ else if(sign > 0)
+ return x==uvinf;
+ else
+ return x==uvneginf;
+}
--- /dev/null
+++ b/libc/print.c
@@ -1,0 +1,15 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+print(char *fmt, ...)
+{+ int n;
+ va_list args;
+
+ va_start(args, fmt);
+ n = vfprint(1, fmt, args);
+ va_end(args);
+ return n;
+}
--- /dev/null
+++ b/libc/rune.c
@@ -1,0 +1,204 @@
+#include <u.h>
+#include <libc.h>
+
+enum
+{+ Bit1 = 7,
+ Bitx = 6,
+ Bit2 = 5,
+ Bit3 = 4,
+ Bit4 = 3,
+ Bit5 = 2,
+
+ T1 = ((1<<(Bit1+1))-1) ^ 0xFF, /* 0000 0000 */
+ Tx = ((1<<(Bitx+1))-1) ^ 0xFF, /* 1000 0000 */
+ T2 = ((1<<(Bit2+1))-1) ^ 0xFF, /* 1100 0000 */
+ T3 = ((1<<(Bit3+1))-1) ^ 0xFF, /* 1110 0000 */
+ T4 = ((1<<(Bit4+1))-1) ^ 0xFF, /* 1111 0000 */
+ T5 = ((1<<(Bit5+1))-1) ^ 0xFF, /* 1111 1000 */
+
+ Rune1 = (1<<(Bit1+0*Bitx))-1, /* 0000 0000 0000 0000 0111 1111 */
+ Rune2 = (1<<(Bit2+1*Bitx))-1, /* 0000 0000 0000 0111 1111 1111 */
+ Rune3 = (1<<(Bit3+2*Bitx))-1, /* 0000 0000 1111 1111 1111 1111 */
+ Rune4 = (1<<(Bit4+3*Bitx))-1, /* 0011 1111 1111 1111 1111 1111 */
+
+ Maskx = (1<<Bitx)-1, /* 0011 1111 */
+ Testx = Maskx ^ 0xFF, /* 1100 0000 */
+
+ Bad = Runeerror,
+};
+
+int
+chartorune(Rune *rune, char *str)
+{+ int c, c1, c2, c3;
+ long l;
+
+ /*
+ * one character sequence
+ * 00000-0007F => T1
+ */
+ c = *(uchar*)str;
+ if(c < Tx) {+ *rune = c;
+ return 1;
+ }
+
+ /*
+ * two character sequence
+ * 0080-07FF => T2 Tx
+ */
+ c1 = *(uchar*)(str+1) ^ Tx;
+ if(c1 & Testx)
+ goto bad;
+ if(c < T3) {+ if(c < T2)
+ goto bad;
+ l = ((c << Bitx) | c1) & Rune2;
+ if(l <= Rune1)
+ goto bad;
+ *rune = l;
+ return 2;
+ }
+
+ /*
+ * three character sequence
+ * 0800-FFFF => T3 Tx Tx
+ */
+ c2 = *(uchar*)(str+2) ^ Tx;
+ if(c2 & Testx)
+ goto bad;
+ if(c < T4) {+ l = ((((c << Bitx) | c1) << Bitx) | c2) & Rune3;
+ if(l <= Rune2)
+ goto bad;
+ *rune = l;
+ return 3;
+ }
+
+ /*
+ * four character sequence
+ * 10000-10FFFF => T4 Tx Tx Tx
+ */
+ if(UTFmax >= 4) {+ c3 = *(uchar*)(str+3) ^ Tx;
+ if(c3 & Testx)
+ goto bad;
+ if(c < T5) {+ l = ((((((c << Bitx) | c1) << Bitx) | c2) << Bitx) | c3) & Rune4;
+ if(l <= Rune3)
+ goto bad;
+ if(l > Runemax)
+ goto bad;
+ *rune = l;
+ return 4;
+ }
+ }
+
+ /*
+ * bad decoding
+ */
+bad:
+ *rune = Bad;
+ return 1;
+}
+
+int
+runetochar(char *str, Rune *rune)
+{+ long c;
+
+ c = *rune;
+ if(c > Runemax)
+ c = Runeerror;
+
+ /*
+ * one character sequence
+ * 00000-0007F => 00-7F
+ */
+ if(c <= Rune1) {+ str[0] = c;
+ return 1;
+ }
+
+ /*
+ * two character sequence
+ * 0080-07FF => T2 Tx
+ */
+ if(c <= Rune2) {+ str[0] = T2 | (c >> 1*Bitx);
+ str[1] = Tx | (c & Maskx);
+ return 2;
+ }
+
+ /*
+ * three character sequence
+ * 0800-FFFF => T3 Tx Tx
+ */
+ if(c <= Rune3) {+ str[0] = T3 | (c >> 2*Bitx);
+ str[1] = Tx | ((c >> 1*Bitx) & Maskx);
+ str[2] = Tx | (c & Maskx);
+ return 3;
+ }
+
+ /*
+ * four character sequence
+ * 10000-1FFFFF => T4 Tx Tx Tx
+ */
+ str[0] = T4 | (c >> 3*Bitx);
+ str[1] = Tx | ((c >> 2*Bitx) & Maskx);
+ str[2] = Tx | ((c >> 1*Bitx) & Maskx);
+ str[3] = Tx | (c & Maskx);
+ return 4;
+}
+
+int
+runelen(long c)
+{+ Rune rune;
+ char str[UTFmax];
+
+ rune = c;
+ return runetochar(str, &rune);
+}
+
+int
+runenlen(Rune *r, int nrune)
+{+ int nb, c;
+
+ nb = 0;
+ while(nrune--) {+ c = *r++;
+ if(c <= Rune1)
+ nb++;
+ else
+ if(c <= Rune2)
+ nb += 2;
+ else
+ if(c <= Rune3 || c > Runemax)
+ nb += 3;
+ else
+ nb += 4;
+ }
+ return nb;
+}
+
+int
+fullrune(char *str, int n)
+{+ int c;
+
+ if(n <= 0)
+ return 0;
+ c = *(uchar*)str;
+ if(c < Tx)
+ return 1;
+ if(c < T3)
+ return n >= 2;
+ if(UTFmax == 3 || c < T4)
+ return n >= 3;
+ return n >= 4;
+}
+
--- /dev/null
+++ b/libc/snprint.c
@@ -1,0 +1,16 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+snprint(char *buf, int len, char *fmt, ...)
+{+ int n;
+ va_list args;
+
+ va_start(args, fmt);
+ n = vsnprint(buf, len, fmt, args);
+ va_end(args);
+ return n;
+}
+
--- /dev/null
+++ b/libc/sprint.c
@@ -1,0 +1,24 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+sprint(char *buf, char *fmt, ...)
+{+ int n;
+ uint len;
+ va_list args;
+
+ len = 1<<30; /* big number, but sprint is deprecated anyway */
+ /*
+ * on PowerPC, the stack is near the top of memory, so
+ * we must be sure not to overflow a 32-bit pointer.
+ */
+ if((uintptr)buf+len < (uintptr)buf)
+ len = -(uintptr)buf-1;
+
+ va_start(args, fmt);
+ n = vsnprint(buf, len, fmt, args);
+ va_end(args);
+ return n;
+}
--- /dev/null
+++ b/libc/strtod.c
@@ -1,0 +1,542 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+/*
+ * This routine will convert to arbitrary precision
+ * floating point entirely in multi-precision fixed.
+ * The answer is the closest floating point number to
+ * the given decimal number. Exactly half way are
+ * rounded ala ieee rules.
+ * Method is to scale input decimal between .500 and .999...
+ * with external power of 2, then binary search for the
+ * closest mantissa to this decimal number.
+ * Nmant is is the required precision. (53 for ieee dp)
+ * Nbits is the max number of bits/word. (must be <= 28)
+ * Prec is calculated - the number of words of fixed mantissa.
+ */
+enum
+{+ Nbits = 28, /* bits safely represented in a ulong */
+ Nmant = 53, /* bits of precision required */
+ Bias = 1022,
+ Prec = (Nmant+Nbits+1)/Nbits, /* words of Nbits each to represent mantissa */
+ Sigbit = 1<<(Prec*Nbits-Nmant), /* first significant bit of Prec-th word */
+ Ndig = 1500,
+ One = (ulong)(1<<Nbits),
+ Half = (ulong)(One>>1),
+ Maxe = 310,
+
+ S0 = 0, /* _ _S0 +S1 #S2 .S3 */
+ S1, /* _+ #S2 .S3 */
+ S2, /* _+# #S2 .S4 eS5 */
+ S3, /* _+. #S4 */
+ S4, /* _+#.# #S4 eS5 */
+ S5, /* _+#.#e +S6 #S7 */
+ S6, /* _+#.#e+ #S7 */
+ S7, /* _+#.#e+# #S7 */
+
+ Fsign = 1<<0, /* found - */
+ Fesign = 1<<1, /* found e- */
+ Fdpoint = 1<<2, /* found . */
+};
+
+static int xcmp(char*, char*);
+static int fpcmp(char*, ulong*);
+static void frnorm(ulong*);
+static void divascii(char*, int*, int*, int*);
+static void mulascii(char*, int*, int*, int*);
+static void divby(char*, int*, int);
+static ulong umuldiv(ulong, ulong, ulong);
+
+typedef struct Tab Tab;
+struct Tab
+{+ int bp;
+ int siz;
+ char* cmp;
+};
+
+#ifndef ERANGE
+#define ERANGE 12345
+#endif
+
+double
+fmtstrtod(const char *as, char **aas)
+{+ int na, ona, ex, dp, bp, c, i, flag, state;
+ ulong low[Prec], hig[Prec], mid[Prec], num, den;
+ double d;
+ char *s, a[Ndig];
+
+ flag = 0; /* Fsign, Fesign, Fdpoint */
+ na = 0; /* number of digits of a[] */
+ dp = 0; /* na of decimal point */
+ ex = 0; /* exonent */
+
+ state = S0;
+ for(s=(char*)as;; s++) {+ c = *s;
+ if(c >= '0' && c <= '9') {+ switch(state) {+ case S0:
+ case S1:
+ case S2:
+ state = S2;
+ break;
+ case S3:
+ case S4:
+ state = S4;
+ break;
+
+ case S5:
+ case S6:
+ case S7:
+ state = S7;
+ ex = ex*10 + (c-'0');
+ continue;
+ }
+ if(na == 0 && c == '0') {+ dp--;
+ continue;
+ }
+ if(na < Ndig-50)
+ a[na++] = c;
+ continue;
+ }
+ switch(c) {+ case '\t':
+ case '\n':
+ case '\v':
+ case '\f':
+ case '\r':
+ case ' ':
+ if(state == S0)
+ continue;
+ break;
+ case '-':
+ if(state == S0)
+ flag |= Fsign;
+ else
+ flag |= Fesign;
+ case '+':
+ if(state == S0)
+ state = S1;
+ else
+ if(state == S5)
+ state = S6;
+ else
+ break; /* syntax */
+ continue;
+ case '.':
+ flag |= Fdpoint;
+ dp = na;
+ if(state == S0 || state == S1) {+ state = S3;
+ continue;
+ }
+ if(state == S2) {+ state = S4;
+ continue;
+ }
+ break;
+ case 'e':
+ case 'E':
+ if(state == S2 || state == S4) {+ state = S5;
+ continue;
+ }
+ break;
+ }
+ break;
+ }
+
+ /*
+ * clean up return char-pointer
+ */
+ switch(state) {+ case S0:
+ if(xcmp(s, "nan") == 0) {+ if(aas != nil)
+ *aas = s+3;
+ goto retnan;
+ }
+ case S1:
+ if(xcmp(s, "infinity") == 0) {+ if(aas != nil)
+ *aas = s+8;
+ goto retinf;
+ }
+ if(xcmp(s, "inf") == 0) {+ if(aas != nil)
+ *aas = s+3;
+ goto retinf;
+ }
+ case S3:
+ if(aas != nil)
+ *aas = (char*)as;
+ goto ret0; /* no digits found */
+ case S6:
+ s--; /* back over +- */
+ case S5:
+ s--; /* back over e */
+ break;
+ }
+ if(aas != nil)
+ *aas = s;
+
+ if(flag & Fdpoint)
+ while(na > 0 && a[na-1] == '0')
+ na--;
+ if(na == 0)
+ goto ret0; /* zero */
+ a[na] = 0;
+ if(!(flag & Fdpoint))
+ dp = na;
+ if(flag & Fesign)
+ ex = -ex;
+ dp += ex;
+ if(dp < -Maxe-Nmant/3){ /* actually -Nmant*log(2)/log(10), but Nmant/3 close enough */+ errno = ERANGE;
+ goto ret0; /* underflow by exp */
+ } else
+ if(dp > +Maxe)
+ goto retinf; /* overflow by exp */
+
+ /*
+ * normalize the decimal ascii number
+ * to range .[5-9][0-9]* e0
+ */
+ bp = 0; /* binary exponent */
+ while(dp > 0)
+ divascii(a, &na, &dp, &bp);
+ while(dp < 0 || a[0] < '5')
+ mulascii(a, &na, &dp, &bp);
+ a[na] = 0;
+
+ /*
+ * very small numbers are represented using
+ * bp = -Bias+1. adjust accordingly.
+ */
+ if(bp < -Bias+1){+ ona = na;
+ divby(a, &na, -bp-Bias+1);
+ if(na < ona){+ memmove(a+ona-na, a, na);
+ memset(a, '0', ona-na);
+ na = ona;
+ }
+ a[na] = 0;
+ bp = -Bias+1;
+ }
+
+ /* close approx by naive conversion */
+ num = 0;
+ den = 1;
+ for(i=0; i<9 && (c=a[i]); i++) {+ num = num*10 + (c-'0');
+ den *= 10;
+ }
+ low[0] = umuldiv(num, One, den);
+ hig[0] = umuldiv(num+1, One, den);
+ for(i=1; i<Prec; i++) {+ low[i] = 0;
+ hig[i] = One-1;
+ }
+
+ /* binary search for closest mantissa */
+ for(;;) {+ /* mid = (hig + low) / 2 */
+ c = 0;
+ for(i=0; i<Prec; i++) {+ mid[i] = hig[i] + low[i];
+ if(c)
+ mid[i] += One;
+ c = mid[i] & 1;
+ mid[i] >>= 1;
+ }
+ frnorm(mid);
+
+ /* compare */
+ c = fpcmp(a, mid);
+ if(c > 0) {+ c = 1;
+ for(i=0; i<Prec; i++)
+ if(low[i] != mid[i]) {+ c = 0;
+ low[i] = mid[i];
+ }
+ if(c)
+ break; /* between mid and hig */
+ continue;
+ }
+ if(c < 0) {+ for(i=0; i<Prec; i++)
+ hig[i] = mid[i];
+ continue;
+ }
+
+ /* only hard part is if even/odd roundings wants to go up */
+ c = mid[Prec-1] & (Sigbit-1);
+ if(c == Sigbit/2 && (mid[Prec-1]&Sigbit) == 0)
+ mid[Prec-1] -= c;
+ break; /* exactly mid */
+ }
+
+ /* normal rounding applies */
+ c = mid[Prec-1] & (Sigbit-1);
+ mid[Prec-1] -= c;
+ if(c >= Sigbit/2) {+ mid[Prec-1] += Sigbit;
+ frnorm(mid);
+ }
+ goto out;
+
+ret0:
+ return 0;
+
+retnan:
+ return __NaN();
+
+retinf:
+ /*
+ * Unix strtod requires these. Plan 9 would return Inf(0) or Inf(-1). */
+ errno = ERANGE;
+ if(flag & Fsign)
+ return -HUGE_VAL;
+ return HUGE_VAL;
+
+out:
+ d = 0;
+ for(i=0; i<Prec; i++)
+ d = d*One + mid[i];
+ if(flag & Fsign)
+ d = -d;
+ d = ldexp(d, bp - Prec*Nbits);
+ if(d == 0){ /* underflow */+ errno = ERANGE;
+ }
+ return d;
+}
+
+static void
+frnorm(ulong *f)
+{+ int i, c;
+
+ c = 0;
+ for(i=Prec-1; i>0; i--) {+ f[i] += c;
+ c = f[i] >> Nbits;
+ f[i] &= One-1;
+ }
+ f[0] += c;
+}
+
+static int
+fpcmp(char *a, ulong* f)
+{+ ulong tf[Prec];
+ int i, d, c;
+
+ for(i=0; i<Prec; i++)
+ tf[i] = f[i];
+
+ for(;;) {+ /* tf *= 10 */
+ for(i=0; i<Prec; i++)
+ tf[i] = tf[i]*10;
+ frnorm(tf);
+ d = (tf[0] >> Nbits) + '0';
+ tf[0] &= One-1;
+
+ /* compare next digit */
+ c = *a;
+ if(c == 0) {+ if('0' < d)+ return -1;
+ if(tf[0] != 0)
+ goto cont;
+ for(i=1; i<Prec; i++)
+ if(tf[i] != 0)
+ goto cont;
+ return 0;
+ }
+ if(c > d)
+ return +1;
+ if(c < d)
+ return -1;
+ a++;
+ cont:;
+ }
+}
+
+static void
+_divby(char *a, int *na, int b)
+{+ int n, c;
+ char *p;
+
+ p = a;
+ n = 0;
+ while(n>>b == 0) {+ c = *a++;
+ if(c == 0) {+ while(n) {+ c = n*10;
+ if(c>>b)
+ break;
+ n = c;
+ }
+ goto xx;
+ }
+ n = n*10 + c-'0';
+ (*na)--;
+ }
+ for(;;) {+ c = n>>b;
+ n -= c<<b;
+ *p++ = c + '0';
+ c = *a++;
+ if(c == 0)
+ break;
+ n = n*10 + c-'0';
+ }
+ (*na)++;
+xx:
+ while(n) {+ n = n*10;
+ c = n>>b;
+ n -= c<<b;
+ *p++ = c + '0';
+ (*na)++;
+ }
+ *p = 0;
+}
+
+static void
+divby(char *a, int *na, int b)
+{+ while(b > 9){+ _divby(a, na, 9);
+ a[*na] = 0;
+ b -= 9;
+ }
+ if(b > 0)
+ _divby(a, na, b);
+}
+
+static Tab tab1[] =
+{+ 1, 0, "",
+ 3, 1, "7",
+ 6, 2, "63",
+ 9, 3, "511",
+ 13, 4, "8191",
+ 16, 5, "65535",
+ 19, 6, "524287",
+ 23, 7, "8388607",
+ 26, 8, "67108863",
+ 27, 9, "134217727",
+};
+
+static void
+divascii(char *a, int *na, int *dp, int *bp)
+{+ int b, d;
+ Tab *t;
+
+ d = *dp;
+ if(d >= (int)(nelem(tab1)))
+ d = (int)(nelem(tab1))-1;
+ t = tab1 + d;
+ b = t->bp;
+ if(memcmp(a, t->cmp, t->siz) > 0)
+ d--;
+ *dp -= d;
+ *bp += b;
+ divby(a, na, b);
+}
+
+static void
+mulby(char *a, char *p, char *q, int b)
+{+ int n, c;
+
+ n = 0;
+ *p = 0;
+ for(;;) {+ q--;
+ if(q < a)
+ break;
+ c = *q - '0';
+ c = (c<<b) + n;
+ n = c/10;
+ c -= n*10;
+ p--;
+ *p = c + '0';
+ }
+ while(n) {+ c = n;
+ n = c/10;
+ c -= n*10;
+ p--;
+ *p = c + '0';
+ }
+}
+
+static Tab tab2[] =
+{+ 1, 1, "", /* dp = 0-0 */
+ 3, 3, "125",
+ 6, 5, "15625",
+ 9, 7, "1953125",
+ 13, 10, "1220703125",
+ 16, 12, "152587890625",
+ 19, 14, "19073486328125",
+ 23, 17, "11920928955078125",
+ 26, 19, "1490116119384765625",
+ 27, 19, "7450580596923828125", /* dp 8-9 */
+};
+
+static void
+mulascii(char *a, int *na, int *dp, int *bp)
+{+ char *p;
+ int d, b;
+ Tab *t;
+
+ d = -*dp;
+ if(d >= (int)(nelem(tab2)))
+ d = (int)(nelem(tab2))-1;
+ t = tab2 + d;
+ b = t->bp;
+ if(memcmp(a, t->cmp, t->siz) < 0)
+ d--;
+ p = a + *na;
+ *bp -= b;
+ *dp += d;
+ *na += d;
+ mulby(a, p+d, p, b);
+}
+
+static int
+xcmp(char *a, char *b)
+{+ int c1, c2;
+
+ while(c1 = *b++) {+ c2 = *a++;
+ if(isupper(c2))
+ c2 = tolower(c2);
+ if(c1 != c2)
+ return 1;
+ }
+ return 0;
+}
+
+static ulong
+umuldiv(ulong a, ulong b, ulong c)
+{+ return ((uvlong)a * (uvlong)b) / c;
+}
--- /dev/null
+++ b/libc/strtod.h
@@ -1,0 +1,4 @@
+extern double __NaN(void);
+extern double __Inf(int);
+extern double __isNaN(double);
+extern double __isInf(double, int);
--- /dev/null
+++ b/libc/sysfatal.c
@@ -1,0 +1,24 @@
+#include <u.h>
+#include <libc.h>
+
+#include <stdlib.h>
+
+static void
+_sysfatalimpl(char *fmt, va_list arg)
+{+ vfprint(2, fmt, arg);
+ fprint(2, "\n");
+ exit(1);
+}
+
+void (*_sysfatal)(char *fmt, va_list arg) = _sysfatalimpl;
+
+void
+sysfatal(char *fmt, ...)
+{+ va_list arg;
+
+ va_start(arg, fmt);
+ (*_sysfatal)(fmt, arg);
+ va_end(arg);
+}
--- /dev/null
+++ b/libc/u16.c
@@ -1,0 +1,69 @@
+#include <u.h>
+#include <libc.h>
+
+#define between(x,min,max) (((min-1-x) & (x-max-1))>>8)
+
+int
+enc16chr(int o)
+{+ int c;
+
+ c = between(o, 0, 9) & ('0'+o);+ c |= between(o, 10, 15) & ('A'+(o-10));+ return c;
+}
+
+int
+dec16chr(int c)
+{+ int o;
+
+ o = between(c, '0', '9') & (1+(c-'0'));
+ o |= between(c, 'A', 'F') & (1+10+(c-'A'));
+ o |= between(c, 'a', 'f') & (1+10+(c-'a'));
+ return o-1;
+}
+
+int
+dec16(uchar *out, int lim, char *in, int n)
+{+ int c, w = 0, i = 0;
+ uchar *start = out;
+ uchar *eout = out + lim;
+
+ while(n-- > 0){+ c = dec16chr(*in++);
+ if(c < 0)
+ continue;
+ w = (w<<4) + c;
+ i++;
+ if(i == 2){+ if(out + 1 > eout)
+ goto exhausted;
+ *out++ = w;
+ w = 0;
+ i = 0;
+ }
+ }
+exhausted:
+ return out - start;
+}
+
+int
+enc16(char *out, int lim, uchar *in, int n)
+{+ uint c;
+ char *eout = out + lim;
+ char *start = out;
+
+ while(n-- > 0){+ c = *in++;
+ if(out + 2 >= eout)
+ goto exhausted;
+ *out++ = enc16chr(c>>4);
+ *out++ = enc16chr(c&15);
+ }
+exhausted:
+ *out = 0;
+ return out - start;
+}
--- /dev/null
+++ b/libc/u32.c
@@ -1,0 +1,132 @@
+#include <u.h>
+#include <libc.h>
+
+#define between(x,min,max) (((min-1-x) & (x-max-1))>>8)
+
+int
+enc32chr(int o)
+{+ int c;
+
+ c = between(o, 0, 25) & ('A'+o);+ c |= between(o, 26, 31) & ('2'+(o-26));+ return c;
+}
+
+int
+dec32chr(int c)
+{+ int o;
+
+ o = between(c, 'A', 'Z') & (1+(c-'A'));
+ o |= between(c, 'a', 'z') & (1+(c-'a'));
+ o |= between(c, '2', '7') & (1+26+(c-'2'));
+ return o-1;
+}
+
+int
+dec32(uchar *dest, int ndest, char *src, int nsrc)
+{+ uchar *start;
+ int i, j, u[8];
+
+ if(ndest+1 < (5*nsrc+7)/8)
+ return -1;
+ start = dest;
+ while(nsrc>=8){+ for(i=0; i<8; i++){+ j = dec32chr(src[i]);
+ if(j < 0)
+ j = 0;
+ u[i] = j;
+ }
+ *dest++ = (u[0]<<3) | (0x7 & (u[1]>>2));
+ *dest++ = ((0x3 & u[1])<<6) | (u[2]<<1) | (0x1 & (u[3]>>4));
+ *dest++ = ((0xf & u[3])<<4) | (0xf & (u[4]>>1));
+ *dest++ = ((0x1 & u[4])<<7) | (u[5]<<2) | (0x3 & (u[6]>>3));
+ *dest++ = ((0x7 & u[6])<<5) | u[7];
+ src += 8;
+ nsrc -= 8;
+ }
+ if(nsrc > 0){+ if(nsrc == 1 || nsrc == 3 || nsrc == 6)
+ return -1;
+ for(i=0; i<nsrc; i++){+ j = dec32chr(src[i]);
+ if(j < 0)
+ j = 0;
+ u[i] = j;
+ }
+ *dest++ = (u[0]<<3) | (0x7 & (u[1]>>2));
+ if(nsrc == 2)
+ goto out;
+ *dest++ = ((0x3 & u[1])<<6) | (u[2]<<1) | (0x1 & (u[3]>>4));
+ if(nsrc == 4)
+ goto out;
+ *dest++ = ((0xf & u[3])<<4) | (0xf & (u[4]>>1));
+ if(nsrc == 5)
+ goto out;
+ *dest++ = ((0x1 & u[4])<<7) | (u[5]<<2) | (0x3 & (u[6]>>3));
+ }
+out:
+ return dest-start;
+}
+
+int
+enc32(char *dest, int ndest, uchar *src, int nsrc)
+{+ char *start;
+ int j;
+
+ if(ndest <= (8*nsrc+4)/5)
+ return -1;
+ start = dest;
+ while(nsrc>=5){+ j = (0x1f & (src[0]>>3));
+ *dest++ = enc32chr(j);
+ j = (0x1c & (src[0]<<2)) | (0x03 & (src[1]>>6));
+ *dest++ = enc32chr(j);
+ j = (0x1f & (src[1]>>1));
+ *dest++ = enc32chr(j);
+ j = (0x10 & (src[1]<<4)) | (0x0f & (src[2]>>4));
+ *dest++ = enc32chr(j);
+ j = (0x1e & (src[2]<<1)) | (0x01 & (src[3]>>7));
+ *dest++ = enc32chr(j);
+ j = (0x1f & (src[3]>>2));
+ *dest++ = enc32chr(j);
+ j = (0x18 & (src[3]<<3)) | (0x07 & (src[4]>>5));
+ *dest++ = enc32chr(j);
+ j = (0x1f & (src[4]));
+ *dest++ = enc32chr(j);
+ src += 5;
+ nsrc -= 5;
+ }
+ if(nsrc){+ j = (0x1f & (src[0]>>3));
+ *dest++ = enc32chr(j);
+ j = (0x1c & (src[0]<<2));
+ if(nsrc == 1)
+ goto out;
+ j |= (0x03 & (src[1]>>6));
+ *dest++ = enc32chr(j);
+ j = (0x1f & (src[1]>>1));
+ *dest++ = enc32chr(j);
+ j = (0x10 & (src[1]<<4));
+ if(nsrc == 2)
+ goto out;
+ j |= (0x0f & (src[2]>>4));
+ *dest++ = enc32chr(j);
+ j = (0x1e & (src[2]<<1));
+ if(nsrc == 3)
+ goto out;
+ j |= (0x01 & (src[3]>>7));
+ *dest++ = enc32chr(j);
+ j = (0x1f & (src[3]>>2));
+ *dest++ = enc32chr(j);
+ j = (0x18 & (src[3]<<3));
+out:
+ *dest++ = enc32chr(j);
+ }
+ *dest = 0;
+ return dest-start;
+}
--- /dev/null
+++ b/libc/u64.c
@@ -1,0 +1,130 @@
+#include <u.h>
+#include <libc.h>
+
+#define between(x,min,max) (((min-1-x) & (x-max-1))>>8)
+
+int
+enc64chr(int o)
+{+ int c;
+
+ c = between(o, 0, 25) & ('A'+o);+ c |= between(o, 26, 51) & ('a'+(o-26));+ c |= between(o, 52, 61) & ('0'+(o-52));+ c |= between(o, 62, 62) & ('+');+ c |= between(o, 63, 63) & ('/');+ return c;
+}
+
+int
+dec64chr(int c)
+{+ int o;
+
+ o = between(c, 'A', 'Z') & (1+(c-'A'));
+ o |= between(c, 'a', 'z') & (1+26+(c-'a'));
+ o |= between(c, '0', '9') & (1+52+(c-'0'));
+ o |= between(c, '+', '+') & (1+62);
+ o |= between(c, '/', '/') & (1+63);
+ return o-1;
+}
+
+int
+dec64(uchar *out, int lim, char *in, int n)
+{+ ulong b24;
+ uchar *start = out;
+ uchar *e = out + lim;
+ int i, c;
+
+ b24 = 0;
+ i = 0;
+ while(n-- > 0){+ c = dec64chr(*in++);
+ if(c < 0)
+ continue;
+ switch(i){+ case 0:
+ b24 = c<<18;
+ break;
+ case 1:
+ b24 |= c<<12;
+ break;
+ case 2:
+ b24 |= c<<6;
+ break;
+ case 3:
+ if(out + 3 > e)
+ goto exhausted;
+
+ b24 |= c;
+ *out++ = b24>>16;
+ *out++ = b24>>8;
+ *out++ = b24;
+ i = 0;
+ continue;
+ }
+ i++;
+ }
+ switch(i){+ case 2:
+ if(out + 1 > e)
+ goto exhausted;
+ *out++ = b24>>16;
+ break;
+ case 3:
+ if(out + 2 > e)
+ goto exhausted;
+ *out++ = b24>>16;
+ *out++ = b24>>8;
+ break;
+ }
+exhausted:
+ return out - start;
+}
+
+int
+enc64(char *out, int lim, uchar *in, int n)
+{+ int i;
+ ulong b24;
+ char *start = out;
+ char *e = out + lim;
+
+ for(i = n/3; i > 0; i--){+ b24 = *in++<<16;
+ b24 |= *in++<<8;
+ b24 |= *in++;
+ if(out + 4 >= e)
+ goto exhausted;
+ *out++ = enc64chr(b24>>18);
+ *out++ = enc64chr((b24>>12)&0x3f);
+ *out++ = enc64chr((b24>>6)&0x3f);
+ *out++ = enc64chr(b24&0x3f);
+ }
+
+ switch(n%3){+ case 2:
+ b24 = *in++<<16;
+ b24 |= *in<<8;
+ if(out + 4 >= e)
+ goto exhausted;
+ *out++ = enc64chr(b24>>18);
+ *out++ = enc64chr((b24>>12)&0x3f);
+ *out++ = enc64chr((b24>>6)&0x3f);
+ *out++ = '=';
+ break;
+ case 1:
+ b24 = *in<<16;
+ if(out + 4 >= e)
+ goto exhausted;
+ *out++ = enc64chr(b24>>18);
+ *out++ = enc64chr((b24>>12)&0x3f);
+ *out++ = '=';
+ *out++ = '=';
+ break;
+ }
+exhausted:
+ *out = 0;
+ return out - start;
+}
--- /dev/null
+++ b/libc/utf.h
@@ -1,0 +1,53 @@
+#ifndef _UTFH_
+#define _UTFH_ 1
+
+typedef unsigned int Rune; /* 32 bits */
+
+enum
+{+ UTFmax = 4, /* maximum bytes per rune */
+ Runesync = 0x80, /* cannot represent part of a UTF sequence (<) */
+ Runeself = 0x80, /* rune and UTF sequences are the same (<) */
+ Runeerror = 0xFFFD, /* decoding error in UTF */
+ Runemax = 0x10FFFF, /* 21-bit rune */
+ Runemask = 0x1FFFFF, /* bits used by runes (see grep) */
+};
+
+/*
+ * rune routines
+ */
+extern int runetochar(char*, Rune*);
+extern int chartorune(Rune*, char*);
+extern int runelen(long);
+extern int runenlen(Rune*, int);
+extern int fullrune(char*, int);
+extern int utflen(char*);
+extern int utfnlen(char*, long);
+extern char* utfrune(char*, long);
+extern char* utfrrune(char*, long);
+extern char* utfutf(char*, char*);
+extern char* utfecpy(char*, char*, char*);
+
+extern Rune* runestrcat(Rune*, Rune*);
+extern Rune* runestrchr(Rune*, Rune);
+extern int runestrcmp(Rune*, Rune*);
+extern Rune* runestrcpy(Rune*, Rune*);
+extern Rune* runestrncpy(Rune*, Rune*, long);
+extern Rune* runestrecpy(Rune*, Rune*, Rune*);
+extern Rune* runestrdup(Rune*);
+extern Rune* runestrncat(Rune*, Rune*, long);
+extern int runestrncmp(Rune*, Rune*, long);
+extern Rune* runestrrchr(Rune*, Rune);
+extern long runestrlen(Rune*);
+extern Rune* runestrstr(Rune*, Rune*);
+
+extern Rune tolowerrune(Rune);
+extern Rune totitlerune(Rune);
+extern Rune toupperrune(Rune);
+extern int isalpharune(Rune);
+extern int islowerrune(Rune);
+extern int isspacerune(Rune);
+extern int istitlerune(Rune);
+extern int isupperrune(Rune);
+
+#endif
--- /dev/null
+++ b/libc/utfdef.h
@@ -1,0 +1,14 @@
+#define uchar _utfuchar
+#define ushort _utfushort
+#define uint _utfuint
+#define ulong _utfulong
+#define vlong _utfvlong
+#define uvlong _utfuvlong
+
+typedef unsigned char uchar;
+typedef unsigned short ushort;
+typedef unsigned int uint;
+typedef unsigned long ulong;
+
+#define nelem(x) (sizeof(x)/sizeof((x)[0]))
+#define nil ((void*)0)
--- /dev/null
+++ b/libc/utflen.c
@@ -1,0 +1,23 @@
+#include <u.h>
+#include <libc.h>
+
+int
+utflen(char *s)
+{+ int c;
+ long n;
+ Rune rune;
+
+ n = 0;
+ for(;;) {+ c = *(uchar*)s;
+ if(c < Runeself) {+ if(c == 0)
+ return n;
+ s++;
+ } else
+ s += chartorune(&rune, s);
+ n++;
+ }
+ return 0;
+}
--- /dev/null
+++ b/libc/vfprint.c
@@ -1,0 +1,19 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+vfprint(int fd, char *fmt, va_list args)
+{+ Fmt f;
+ char buf[256];
+ int n;
+
+ fmtfdinit(&f, fd, buf, sizeof(buf));
+ VA_COPY(f.args,args);
+ n = dofmt(&f, fmt);
+ VA_END(f.args);
+ if(n > 0 && __fmtFdFlush(&f) == 0)
+ return -1;
+ return n;
+}
--- /dev/null
+++ b/libc/vsnprint.c
@@ -1,0 +1,24 @@
+#include <u.h>
+#include <libc.h>
+#include "fmtdef.h"
+
+int
+vsnprint(char *buf, int len, char *fmt, va_list args)
+{+ Fmt f;
+
+ if(len <= 0)
+ return -1;
+ f.runes = 0;
+ f.start = buf;
+ f.to = buf;
+ f.stop = buf + len - 1;
+ f.flush = 0;
+ f.farg = nil;
+ f.nfmt = 0;
+ VA_COPY(f.args,args);
+ dofmt(&f, fmt);
+ VA_END(f.args);
+ *(char*)f.to = '\0';
+ return (char*)f.to - buf;
+}
--- /dev/null
+++ b/libmp/betomp.c
@@ -1,0 +1,34 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// convert a big-endian byte array (most significant byte first) to an mpint
+mpint*
+betomp(uchar *p, uint n, mpint *b)
+{+ int m, s;
+ mpdigit x;
+
+ if(b == nil){+ b = mpnew(0);
+ setmalloctag(b, getcallerpc(&p));
+ }
+ mpbits(b, n*8);
+
+ m = DIGITS(n*8);
+ b->top = m--;
+ b->sign = 1;
+
+ s = ((n-1)*8)%Dbits;
+ x = 0;
+ for(; n > 0; n--){+ x |= ((mpdigit)(*p++)) << s;
+ s -= 8;
+ if(s < 0){+ b->p[m--] = x;
+ s = Dbits-8;
+ x = 0;
+ }
+ }
+ return mpnorm(b);
+}
--- /dev/null
+++ b/libmp/cnfield.c
@@ -1,0 +1,114 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+/*
+ * fast reduction for crandall numbers of the form: 2^n - c
+ */
+
+enum {+ MAXDIG = 1024 / Dbits,
+};
+
+typedef struct CNfield CNfield;
+struct CNfield
+{+ Mfield f;
+
+ mpint m[1];
+
+ int s;
+ mpdigit c;
+};
+
+static int
+cnreduce(Mfield *m, mpint *a, mpint *r)
+{+ mpdigit q[MAXDIG-1], t[MAXDIG], d;
+ CNfield *f = (CNfield*)m;
+ int qn, tn, k;
+
+ k = f->f.m.top;
+ if((a->top - k) >= MAXDIG)
+ return -1;
+
+ mpleft(a, f->s, r);
+ if(r->top <= k)
+ mpbits(r, (k+1)*Dbits);
+
+ /* q = hi(r) */
+ qn = r->top - k;
+ memmove(q, r->p+k, qn*Dbytes);
+
+ /* r = lo(r) */
+ r->top = k;
+ r->sign = 1;
+
+ do {+ /* t = q*c */
+ tn = qn+1;
+ memset(t, 0, tn*Dbytes);
+ mpvecdigmuladd(q, qn, f->c, t);
+
+ /* q = hi(t) */
+ qn = tn - k;
+ if(qn <= 0) qn = 0;
+ else memmove(q, t+k, qn*Dbytes);
+
+ /* r += lo(t) */
+ if(tn > k)
+ tn = k;
+ mpvecadd(r->p, k, t, tn, r->p);
+
+ /* if(r >= m) r -= m */
+ mpvecsub(r->p, k+1, f->m->p, k, t);
+ d = t[k];
+ for(tn = 0; tn < k; tn++)
+ r->p[tn] = (r->p[tn] & d) | (t[tn] & ~d);
+ } while(qn > 0);
+
+ if(f->s != 0)
+ mpright(r, f->s, r);
+ mpnorm(r);
+
+ return 0;
+}
+
+Mfield*
+cnfield(mpint *N)
+{+ mpint *M, *C;
+ CNfield *f;
+ mpdigit d;
+ int s;
+
+ if(N->top <= 2 || N->top >= MAXDIG)
+ return nil;
+ f = nil;
+ d = N->p[N->top-1];
+ for(s = 0; (d & (mpdigit)1<<Dbits-1) == 0; s++)
+ d <<= 1;
+ C = mpnew(0);
+ M = mpcopy(N);
+ mpleft(N, s, M);
+ mpleft(mpone, M->top*Dbits, C);
+ mpsub(C, M, C);
+ if(C->top != 1)
+ goto out;
+ f = mallocz(sizeof(CNfield) + M->top*sizeof(mpdigit), 1);
+ if(f == nil)
+ goto out;
+ f->s = s;
+ f->c = C->p[0];
+ f->m->size = M->top;
+ f->m->p = (mpdigit*)&f[1];
+ mpassign(M, f->m);
+ mpassign(N, (mpint*)f);
+ f->f.reduce = cnreduce;
+ f->f.m.flags |= MPfield;
+out:
+ mpfree(M);
+ mpfree(C);
+
+ return (Mfield*)f;
+}
--- /dev/null
+++ b/libmp/dat.h
@@ -1,0 +1,12 @@
+#define mpdighi (mpdigit)(1<<(Dbits-1))
+#define DIGITS(x) ((Dbits - 1 + (x))/Dbits)
+
+// for converting between int's and mpint's
+#define MAXUINT ((uint)-1)
+#define MAXINT (MAXUINT>>1)
+#define MININT (MAXINT+1)
+
+// for converting between vlongs's and mpint's
+#define MAXUVLONG (~0ULL)
+#define MAXVLONG (MAXUVLONG>>1)
+#define MINVLONG (MAXVLONG+1ULL)
--- /dev/null
+++ b/libmp/gmfield.c
@@ -1,0 +1,173 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+/*
+ * fast reduction for generalized mersenne numbers (GM)
+ * using a series of additions and subtractions.
+ */
+
+enum {+ MAXDIG = 1024/Dbits,
+};
+
+typedef struct GMfield GMfield;
+struct GMfield
+{+ Mfield f;
+
+ mpint m2[1];
+
+ int nadd;
+ int nsub;
+ int indx[256];
+};
+
+static int
+gmreduce(Mfield *m, mpint *a, mpint *r)
+{+ GMfield *g = (GMfield*)m;
+ mpdigit d0, t[MAXDIG];
+ int i, j, d, *x;
+
+ if(mpmagcmp(a, g->m2) >= 0)
+ return -1;
+
+ if(a != r)
+ mpassign(a, r);
+
+ d = g->f.m.top;
+ mpbits(r, (d+1)*Dbits*2);
+ memmove(t+d, r->p+d, d*Dbytes);
+
+ r->sign = 1;
+ r->top = d;
+ r->p[d] = 0;
+
+ if(g->nsub > 0)
+ mpvecdigmuladd(g->f.m.p, d, g->nsub, r->p);
+
+ x = g->indx;
+ for(i=0; i<g->nadd; i++){+ t[0] = 0;
+ d0 = t[*x++];
+ for(j=1; j<d; j++)
+ t[j] = t[*x++];
+ t[0] = d0;
+
+ mpvecadd(r->p, d+1, t, d, r->p);
+ }
+
+ for(i=0; i<g->nsub; i++){+ t[0] = 0;
+ d0 = t[*x++];
+ for(j=1; j<d; j++)
+ t[j] = t[*x++];
+ t[0] = d0;
+
+ mpvecsub(r->p, d+1, t, d, r->p);
+ }
+
+ mpvecdigmulsub(g->f.m.p, d, r->p[d], r->p);
+ r->p[d] = 0;
+
+ mpvecsub(r->p, d+1, g->f.m.p, d, r->p+d+1);
+ d0 = r->p[2*d+1];
+ for(j=0; j<d; j++)
+ r->p[j] = (r->p[j] & d0) | (r->p[j+d+1] & ~d0);
+
+ mpnorm(r);
+
+ return 0;
+}
+
+Mfield*
+gmfield(mpint *N)
+{+ int i,j,d, s, *C, *X, *x, *e;
+ mpint *M, *T;
+ GMfield *g;
+
+ d = N->top;
+ if(d <= 2 || d > MAXDIG/2 || (mpsignif(N) % Dbits) != 0)
+ return nil;
+ g = nil;
+ T = mpnew(0);
+ M = mpcopy(N);
+ C = malloc(sizeof(int)*(d+1));
+ X = malloc(sizeof(int)*(d*d));
+ if(C == nil || X == nil)
+ goto out;
+
+ for(i=0; i<=d; i++){+ if((M->p[i]>>8) != 0 && (~M->p[i]>>8) != 0)
+ goto out;
+ j = M->p[i];
+ C[d - i] = -j;
+ itomp(j, T);
+ mpleft(T, i*Dbits, T);
+ mpsub(M, T, M);
+ }
+ for(j=0; j<d; j++)
+ X[j] = C[d-j];
+ for(i=1; i<d; i++){+ X[d*i] = X[d*(i-1) + d-1]*C[d];
+ for(j=1; j<d; j++)
+ X[d*i + j] = X[d*(i-1) + j-1] + X[d*(i-1) + d-1]*C[d-j];
+ }
+ g = mallocz(sizeof(GMfield) + (d+1)*sizeof(mpdigit)*2, 1);
+ if(g == nil)
+ goto out;
+
+ g->m2->p = (mpdigit*)&g[1];
+ g->m2->size = d*2+1;
+ mpmul(N, N, g->m2);
+ mpassign(N, (mpint*)g);
+ g->f.reduce = gmreduce;
+ g->f.m.flags |= MPfield;
+
+ s = 0;
+ x = g->indx;
+ e = x + nelem(g->indx) - d;
+ for(g->nadd=0; x <= e; x += d, g->nadd++){+ s = 0;
+ for(i=0; i<d; i++){+ for(j=0; j<d; j++){+ if(X[d*i+j] > 0 && x[j] == 0){+ X[d*i+j]--;
+ x[j] = d+i;
+ s = 1;
+ break;
+ }
+ }
+ }
+ if(s == 0)
+ break;
+ }
+ for(g->nsub=0; x <= e; x += d, g->nsub++){+ s = 0;
+ for(i=0; i<d; i++){+ for(j=0; j<d; j++){+ if(X[d*i+j] < 0 && x[j] == 0){+ X[d*i+j]++;
+ x[j] = d+i;
+ s = 1;
+ break;
+ }
+ }
+ }
+ if(s == 0)
+ break;
+ }
+ if(s != 0){+ mpfree((mpint*)g);
+ g = nil;
+ }
+out:
+ free(C);
+ free(X);
+ mpfree(M);
+ mpfree(T);
+ return (Mfield*)g;
+}
+
--- /dev/null
+++ b/libmp/letomp.c
@@ -1,0 +1,31 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// convert a little endian byte array (least significant byte first) to an mpint
+mpint*
+letomp(uchar *s, uint n, mpint *b)
+{+ int i=0, m = 0;
+ mpdigit x=0;
+
+ if(b == nil){+ b = mpnew(0);
+ setmalloctag(b, getcallerpc(&s));
+ }
+ mpbits(b, 8*n);
+ for(; n > 0; n--){+ x |= ((mpdigit)(*s++)) << i;
+ i += 8;
+ if(i == Dbits){+ b->p[m++] = x;
+ i = 0;
+ x = 0;
+ }
+ }
+ if(i > 0)
+ b->p[m++] = x;
+ b->top = m;
+ b->sign = 1;
+ return mpnorm(b);
+}
--- /dev/null
+++ b/libmp/mpadd.c
@@ -1,0 +1,58 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// sum = abs(b1) + abs(b2), i.e., add the magnitudes
+void
+mpmagadd(mpint *b1, mpint *b2, mpint *sum)
+{+ int m, n;
+ mpint *t;
+
+ sum->flags |= (b1->flags | b2->flags) & MPtimesafe;
+
+ // get the sizes right
+ if(b2->top > b1->top){+ t = b1;
+ b1 = b2;
+ b2 = t;
+ }
+ n = b1->top;
+ m = b2->top;
+ if(n == 0){+ mpassign(mpzero, sum);
+ return;
+ }
+ if(m == 0){+ mpassign(b1, sum);
+ sum->sign = 1;
+ return;
+ }
+ mpbits(sum, (n+1)*Dbits);
+ sum->top = n+1;
+
+ mpvecadd(b1->p, n, b2->p, m, sum->p);
+ sum->sign = 1;
+
+ mpnorm(sum);
+}
+
+// sum = b1 + b2
+void
+mpadd(mpint *b1, mpint *b2, mpint *sum)
+{+ int sign;
+
+ if(b1->sign != b2->sign){+ assert(((b1->flags | b2->flags | sum->flags) & MPtimesafe) == 0);
+ if(b1->sign < 0)
+ mpmagsub(b2, b1, sum);
+ else
+ mpmagsub(b1, b2, sum);
+ } else {+ sign = b1->sign;
+ mpmagadd(b1, b2, sum);
+ if(sum->top != 0)
+ sum->sign = sign;
+ }
+}
--- /dev/null
+++ b/libmp/mpaux.c
@@ -1,0 +1,205 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+static mpdigit _mptwodata[1] = { 2 };+static mpint _mptwo =
+{+ 1, 1, 1,
+ _mptwodata,
+ MPstatic|MPnorm
+};
+mpint *mptwo = &_mptwo;
+
+static mpdigit _mponedata[1] = { 1 };+static mpint _mpone =
+{+ 1, 1, 1,
+ _mponedata,
+ MPstatic|MPnorm
+};
+mpint *mpone = &_mpone;
+
+static mpdigit _mpzerodata[1] = { 0 };+static mpint _mpzero =
+{+ 1, 1, 0,
+ _mpzerodata,
+ MPstatic|MPnorm
+};
+mpint *mpzero = &_mpzero;
+
+static int mpmindigits = 33;
+
+// set minimum digit allocation
+void
+mpsetminbits(int n)
+{+ if(n < 0)
+ sysfatal("mpsetminbits: n < 0");+ if(n == 0)
+ n = 1;
+ mpmindigits = DIGITS(n);
+}
+
+// allocate an n bit 0'd number
+mpint*
+mpnew(int n)
+{+ mpint *b;
+
+ if(n < 0)
+ sysfatal("mpsetminbits: n < 0");+
+ n = DIGITS(n);
+ if(n < mpmindigits)
+ n = mpmindigits;
+ b = mallocz(sizeof(mpint) + n*Dbytes, 1);
+ if(b == nil)
+ sysfatal("mpnew: %r");+ setmalloctag(b, getcallerpc(&n));
+ b->p = (mpdigit*)&b[1];
+ b->size = n;
+ b->sign = 1;
+ b->flags = MPnorm;
+
+ return b;
+}
+
+// guarantee at least n significant bits
+void
+mpbits(mpint *b, int m)
+{+ int n;
+
+ n = DIGITS(m);
+ if(b->size >= n){+ if(b->top >= n)
+ return;
+ } else {+ if(b->p == (mpdigit*)&b[1]){+ b->p = (mpdigit*)mallocz(n*Dbytes, 0);
+ if(b->p == nil)
+ sysfatal("mpbits: %r");+ memmove(b->p, &b[1], Dbytes*b->top);
+ memset(&b[1], 0, Dbytes*b->size);
+ } else {+ b->p = (mpdigit*)realloc(b->p, n*Dbytes);
+ if(b->p == nil)
+ sysfatal("mpbits: %r");+ }
+ b->size = n;
+ }
+ memset(&b->p[b->top], 0, Dbytes*(n - b->top));
+ b->top = n;
+ b->flags &= ~MPnorm;
+}
+
+void
+mpfree(mpint *b)
+{+ if(b == nil)
+ return;
+ if(b->flags & MPstatic)
+ sysfatal("freeing mp constant");+ memset(b->p, 0, b->size*Dbytes);
+ if(b->p != (mpdigit*)&b[1])
+ free(b->p);
+ free(b);
+}
+
+mpint*
+mpnorm(mpint *b)
+{+ int i;
+
+ if(b->flags & MPtimesafe){+ assert(b->sign == 1);
+ b->flags &= ~MPnorm;
+ return b;
+ }
+ for(i = b->top-1; i >= 0; i--)
+ if(b->p[i] != 0)
+ break;
+ b->top = i+1;
+ if(b->top == 0)
+ b->sign = 1;
+ b->flags |= MPnorm;
+ return b;
+}
+
+mpint*
+mpcopy(mpint *old)
+{+ mpint *new;
+
+ new = mpnew(Dbits*old->size);
+ setmalloctag(new, getcallerpc(&old));
+ new->sign = old->sign;
+ new->top = old->top;
+ new->flags = old->flags & ~(MPstatic|MPfield);
+ memmove(new->p, old->p, Dbytes*old->top);
+ return new;
+}
+
+void
+mpassign(mpint *old, mpint *new)
+{+ if(new == nil || old == new)
+ return;
+ new->top = 0;
+ mpbits(new, Dbits*old->top);
+ new->sign = old->sign;
+ new->top = old->top;
+ new->flags &= ~MPnorm;
+ new->flags |= old->flags & ~(MPstatic|MPfield);
+ memmove(new->p, old->p, Dbytes*old->top);
+}
+
+// number of significant bits in mantissa
+int
+mpsignif(mpint *n)
+{+ int i, j;
+ mpdigit d;
+
+ if(n->top == 0)
+ return 0;
+ for(i = n->top-1; i >= 0; i--){+ d = n->p[i];
+ for(j = Dbits-1; j >= 0; j--){+ if(d & (((mpdigit)1)<<j))
+ return i*Dbits + j + 1;
+ }
+ }
+ return 0;
+}
+
+// k, where n = 2**k * q for odd q
+int
+mplowbits0(mpint *n)
+{+ int k, bit, digit;
+ mpdigit d;
+
+ assert(n->flags & MPnorm);
+ if(n->top==0)
+ return 0;
+ k = 0;
+ bit = 0;
+ digit = 0;
+ d = n->p[0];
+ for(;;){+ if(d & (1<<bit))
+ break;
+ k++;
+ bit++;
+ if(bit==Dbits){+ if(++digit >= n->top)
+ return 0;
+ d = n->p[digit];
+ bit = 0;
+ }
+ }
+ return k;
+}
--- /dev/null
+++ b/libmp/mpcmp.c
@@ -1,0 +1,30 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// return neg, 0, pos as abs(b1)-abs(b2) is neg, 0, pos
+int
+mpmagcmp(mpint *b1, mpint *b2)
+{+ int i;
+
+ i = b1->flags | b2->flags;
+ if(i & MPtimesafe)
+ return mpvectscmp(b1->p, b1->top, b2->p, b2->top);
+ if(i & MPnorm){+ i = b1->top - b2->top;
+ if(i)
+ return i;
+ }
+ return mpveccmp(b1->p, b1->top, b2->p, b2->top);
+}
+
+// return neg, 0, pos as b1-b2 is neg, 0, pos
+int
+mpcmp(mpint *b1, mpint *b2)
+{+ int sign;
+
+ sign = (b1->sign - b2->sign) >> 1; // -1, 0, 1
+ return sign | (sign&1)-1 & mpmagcmp(b1, b2)*b1->sign;
+}
--- /dev/null
+++ b/libmp/mpdigdiv.c
@@ -1,0 +1,56 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+//
+// divide two digits by one and return quotient
+//
+void
+mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
+{+ mpdigit hi, lo, q, x, y;
+ int i;
+
+ hi = dividend[1];
+ lo = dividend[0];
+
+ // return highest digit value if the result >= 2**32
+ if(hi >= divisor || divisor == 0){+ divisor = 0;
+ *quotient = ~divisor;
+ return;
+ }
+
+ // very common case
+ if(~divisor == 0){+ lo += hi;
+ if(lo < hi){+ hi++;
+ lo++;
+ }
+ if(lo+1 == 0)
+ hi++;
+ *quotient = hi;
+ return;
+ }
+
+ // at this point we know that hi < divisor
+ // just shift and subtract till we're done
+ q = 0;
+ x = divisor;
+ for(i = Dbits-1; hi > 0 && i >= 0; i--){+ x >>= 1;
+ if(x > hi)
+ continue;
+ y = divisor<<i;
+ if(x == hi && y > lo)
+ continue;
+ if(y > lo)
+ hi--;
+ lo -= y;
+ hi -= x;
+ q |= 1<<i;
+ }
+ q += lo/divisor;
+ *quotient = q;
+}
--- /dev/null
+++ b/libmp/mpdiv.c
@@ -1,0 +1,142 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// division ala knuth, seminumerical algorithms, pp 237-238
+// the numbers are stored backwards to what knuth expects so j
+// counts down rather than up.
+
+void
+mpdiv(mpint *dividend, mpint *divisor, mpint *quotient, mpint *remainder)
+{+ int j, s, vn, sign, qsign, rsign;
+ mpdigit qd, *up, *vp, *qp;
+ mpint *u, *v, *t;
+
+ assert(quotient != remainder);
+ assert(divisor->flags & MPnorm);
+
+ // divide bv zero
+ if(divisor->top == 0)
+ abort();
+
+ // division by one or small powers of two
+ if(divisor->top == 1 && (divisor->p[0] & divisor->p[0]-1) == 0){+ vlong r = 0;
+ if(dividend->top > 0)
+ r = (vlong)dividend->sign * (dividend->p[0] & divisor->p[0]-1);
+ if(quotient != nil){+ sign = divisor->sign;
+ for(s = 0; ((divisor->p[0] >> s) & 1) == 0; s++)
+ ;
+ mpright(dividend, s, quotient);
+ if(sign < 0)
+ quotient->sign ^= (-mpmagcmp(quotient, mpzero) >> 31) << 1;
+ }
+ if(remainder != nil){+ remainder->flags |= dividend->flags & MPtimesafe;
+ vtomp(r, remainder);
+ }
+ return;
+ }
+ assert((dividend->flags & MPtimesafe) == 0);
+
+ // quick check
+ if(mpmagcmp(dividend, divisor) < 0){+ if(remainder != nil)
+ mpassign(dividend, remainder);
+ if(quotient != nil)
+ mpassign(mpzero, quotient);
+ return;
+ }
+
+ qsign = divisor->sign * dividend->sign;
+ rsign = dividend->sign;
+
+ // D1: shift until divisor, v, has hi bit set (needed to make trial
+ // divisor accurate)
+ qd = divisor->p[divisor->top-1];
+ for(s = 0; (qd & mpdighi) == 0; s++)
+ qd <<= 1;
+ u = mpnew((dividend->top+2)*Dbits + s);
+ if(s == 0 && divisor != quotient && divisor != remainder) {+ mpassign(dividend, u);
+ v = divisor;
+ } else {+ mpleft(dividend, s, u);
+ v = mpnew(divisor->top*Dbits);
+ mpleft(divisor, s, v);
+ }
+ up = u->p+u->top-1;
+ vp = v->p+v->top-1;
+ vn = v->top;
+
+ // D1a: make sure high digit of dividend is less than high digit of divisor
+ if(*up >= *vp){+ *++up = 0;
+ u->top++;
+ }
+
+ // storage for multiplies
+ t = mpnew(4*Dbits);
+
+ qp = nil;
+ if(quotient != nil){+ mpbits(quotient, (u->top - v->top)*Dbits);
+ quotient->top = u->top - v->top;
+ qp = quotient->p+quotient->top-1;
+ }
+
+ // D2, D7: loop on length of dividend
+ for(j = u->top; j > vn; j--){+
+ // D3: calculate trial divisor
+ mpdigdiv(up-1, *vp, &qd);
+
+ // D3a: rule out trial divisors 2 greater than real divisor
+ if(vn > 1) for(;;){+ memset(t->p, 0, 3*Dbytes); // mpvecdigmuladd adds to what's there
+ mpvecdigmuladd(vp-1, 2, qd, t->p);
+ if(mpveccmp(t->p, 3, up-2, 3) > 0)
+ qd--;
+ else
+ break;
+ }
+
+ // D4: u -= v*qd << j*Dbits
+ sign = mpvecdigmulsub(v->p, vn, qd, up-vn);
+ if(sign < 0){+
+ // D6: trial divisor was too high, add back borrowed
+ // value and decrease divisor
+ mpvecadd(up-vn, vn+1, v->p, vn, up-vn);
+ qd--;
+ }
+
+ // D5: save quotient digit
+ if(qp != nil)
+ *qp-- = qd;
+
+ // push top of u down one
+ u->top--;
+ *up-- = 0;
+ }
+ if(qp != nil){+ assert((quotient->flags & MPtimesafe) == 0);
+ mpnorm(quotient);
+ if(quotient->top != 0)
+ quotient->sign = qsign;
+ }
+
+ if(remainder != nil){+ assert((remainder->flags & MPtimesafe) == 0);
+ mpright(u, s, remainder); // u is the remainder shifted
+ if(remainder->top != 0)
+ remainder->sign = rsign;
+ }
+
+ mpfree(t);
+ mpfree(u);
+ if(v != divisor)
+ mpfree(v);
+}
--- /dev/null
+++ b/libmp/mpexp.c
@@ -1,0 +1,96 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// res = b**e
+//
+// knuth, vol 2, pp 398-400
+
+enum {+ Freeb= 0x1,
+ Freee= 0x2,
+ Freem= 0x4,
+};
+
+//int expdebug;
+
+void
+mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
+{+ mpint *t[2];
+ int tofree;
+ mpdigit d, bit;
+ int i, j;
+
+ assert(m == nil || m->flags & MPnorm);
+ assert((e->flags & MPtimesafe) == 0);
+ res->flags |= b->flags & MPtimesafe;
+
+ i = mpcmp(e,mpzero);
+ if(i==0){+ mpassign(mpone, res);
+ return;
+ }
+ if(i<0)
+ sysfatal("mpexp: negative exponent");+
+ t[0] = mpcopy(b);
+ t[1] = res;
+
+ tofree = 0;
+ if(res == b){+ b = mpcopy(b);
+ tofree |= Freeb;
+ }
+ if(res == e){+ e = mpcopy(e);
+ tofree |= Freee;
+ }
+ if(res == m){+ m = mpcopy(m);
+ tofree |= Freem;
+ }
+
+ // skip first bit
+ i = e->top-1;
+ d = e->p[i];
+ for(bit = mpdighi; (bit & d) == 0; bit >>= 1)
+ ;
+ bit >>= 1;
+
+ j = 0;
+ for(;;){+ for(; bit != 0; bit >>= 1){+ if(m != nil)
+ mpmodmul(t[j], t[j], m, t[j^1]);
+ else
+ mpmul(t[j], t[j], t[j^1]);
+ if(bit & d) {+ if(m != nil)
+ mpmodmul(t[j^1], b, m, t[j]);
+ else
+ mpmul(t[j^1], b, t[j]);
+ } else
+ j ^= 1;
+ }
+ if(--i < 0)
+ break;
+ bit = mpdighi;
+ d = e->p[i];
+ }
+ if(t[j] == res){+ mpfree(t[j^1]);
+ } else {+ mpassign(t[j], res);
+ mpfree(t[j]);
+ }
+
+ if(tofree){+ if(tofree & Freeb)
+ mpfree(b);
+ if(tofree & Freee)
+ mpfree(e);
+ if(tofree & Freem)
+ mpfree(m);
+ }
+}
--- /dev/null
+++ b/libmp/mpextendedgcd.c
@@ -1,0 +1,115 @@
+#include "os.h"
+#include <mp.h>
+
+#define iseven(a) (((a)->p[0] & 1) == 0)
+
+// extended binary gcd
+//
+// For a and b it solves, v = gcd(a,b) and finds x and y s.t.
+// ax + by = v
+//
+// Handbook of Applied Cryptography, Menezes et al, 1997, pg 608.
+void
+mpextendedgcd(mpint *a, mpint *b, mpint *v, mpint *x, mpint *y)
+{+ mpint *u, *A, *B, *C, *D;
+ int g;
+
+ if(v == nil){+ v = mpnew(0);
+ mpextendedgcd(a, b, v, x, y);
+ mpfree(v);
+ return;
+ }
+ assert(x == nil || (x->flags & MPtimesafe) == 0);
+ assert(y == nil || (y->flags & MPtimesafe) == 0);
+ assert((a->flags&b->flags) & MPnorm);
+ assert(((a->flags|b->flags|v->flags) & MPtimesafe) == 0);
+
+ if(a->sign < 0 || b->sign < 0){+ mpassign(mpzero, v);
+ mpassign(mpzero, y);
+ mpassign(mpzero, x);
+ return;
+ }
+
+ if(a->top == 0){+ mpassign(b, v);
+ mpassign(mpone, y);
+ mpassign(mpzero, x);
+ return;
+ }
+ if(b->top == 0){+ mpassign(a, v);
+ mpassign(mpone, x);
+ mpassign(mpzero, y);
+ return;
+ }
+
+ g = 0;
+ a = mpcopy(a);
+ b = mpcopy(b);
+
+ while(iseven(a) && iseven(b)){+ mpright(a, 1, a);
+ mpright(b, 1, b);
+ g++;
+ }
+
+ u = mpcopy(a);
+ mpassign(b, v);
+ A = mpcopy(mpone);
+ B = mpcopy(mpzero);
+ C = mpcopy(mpzero);
+ D = mpcopy(mpone);
+
+ for(;;) {+// print("%B %B %B %B %B %B\n", u, v, A, B, C, D);+ while(iseven(u)){+ mpright(u, 1, u);
+ if(!iseven(A) || !iseven(B)) {+ mpadd(A, b, A);
+ mpsub(B, a, B);
+ }
+ mpright(A, 1, A);
+ mpright(B, 1, B);
+ }
+
+// print("%B %B %B %B %B %B\n", u, v, A, B, C, D);+ while(iseven(v)){+ mpright(v, 1, v);
+ if(!iseven(C) || !iseven(D)) {+ mpadd(C, b, C);
+ mpsub(D, a, D);
+ }
+ mpright(C, 1, C);
+ mpright(D, 1, D);
+ }
+
+// print("%B %B %B %B %B %B\n", u, v, A, B, C, D);+ if(mpcmp(u, v) >= 0){+ mpsub(u, v, u);
+ mpsub(A, C, A);
+ mpsub(B, D, B);
+ } else {+ mpsub(v, u, v);
+ mpsub(C, A, C);
+ mpsub(D, B, D);
+ }
+
+ if(u->top == 0)
+ break;
+
+ }
+ mpassign(C, x);
+ mpassign(D, y);
+ mpleft(v, g, v);
+
+ mpfree(A);
+ mpfree(B);
+ mpfree(C);
+ mpfree(D);
+ mpfree(u);
+ mpfree(a);
+ mpfree(b);
+}
--- /dev/null
+++ b/libmp/mpfield.c
@@ -1,0 +1,21 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+mpint*
+mpfield(mpint *N)
+{+ Mfield *f;
+
+ if(N == nil || N->flags & (MPfield|MPstatic))
+ return N;
+ if((f = cnfield(N)) != nil)
+ goto Exchange;
+ if((f = gmfield(N)) != nil)
+ goto Exchange;
+ return N;
+Exchange:
+ setmalloctag(f, getcallerpc(&N));
+ mpfree(N);
+ return (mpint*)f;
+}
--- /dev/null
+++ b/libmp/mpfmt.c
@@ -1,0 +1,254 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+static int
+toencx(mpint *b, char *buf, int len, int (*enc)(char*, int, uchar*, int))
+{+ uchar *p;
+ int n, rv;
+
+ p = nil;
+ n = mptobe(b, nil, 0, &p);
+ if(n < 0)
+ return -1;
+ rv = (*enc)(buf, len, p, n);
+ free(p);
+ return rv;
+}
+
+static int
+topow2(mpint *b, char *buf, int len, int s)
+{+ mpdigit *p, x;
+ int i, j, sn;
+ char *out, *eout;
+
+ if(len < 1)
+ return -1;
+
+ sn = 1<<s;
+ out = buf;
+ eout = buf+len;
+ for(p = &b->p[b->top-1]; p >= b->p; p--){+ x = *p;
+ for(i = Dbits-s; i >= 0; i -= s){+ j = x >> i & sn - 1;
+ if(j != 0 || out != buf){+ if(out >= eout)
+ return -1;
+ *out++ = enc16chr(j);
+ }
+ }
+ }
+ if(out == buf)
+ *out++ = '0';
+ if(out >= eout)
+ return -1;
+ *out = 0;
+ return 0;
+}
+
+static char*
+modbillion(int rem, ulong r, char *out, char *buf)
+{+ ulong rr;
+ int i;
+
+ for(i = 0; i < 9; i++){+ rr = r%10;
+ r /= 10;
+ if(out <= buf)
+ return nil;
+ *--out = '0' + rr;
+ if(rem == 0 && r == 0)
+ break;
+ }
+ return out;
+}
+
+static int
+to10(mpint *b, char *buf, int len)
+{+ mpint *d, *r, *billion;
+ char *out;
+
+ if(len < 1)
+ return -1;
+
+ d = mpcopy(b);
+ d->flags &= ~MPtimesafe;
+ mpnorm(d);
+ r = mpnew(0);
+ billion = uitomp(1000000000, nil);
+ out = buf+len;
+ *--out = 0;
+ do {+ mpdiv(d, billion, d, r);
+ out = modbillion(d->top, r->p[0], out, buf);
+ if(out == nil)
+ break;
+ } while(d->top != 0);
+ mpfree(d);
+ mpfree(r);
+ mpfree(billion);
+
+ if(out == nil)
+ return -1;
+ len -= out-buf;
+ if(out != buf)
+ memmove(buf, out, len);
+ return 0;
+}
+
+static int
+to8(mpint *b, char *buf, int len)
+{+ mpdigit x, y;
+ char *out;
+ int i, j;
+
+ if(len < 2)
+ return -1;
+
+ out = buf+len;
+ *--out = 0;
+
+ i = j = 0;
+ x = y = 0;
+ while(j < b->top){+ y = b->p[j++];
+ if(i > 0)
+ x |= y << i;
+ else
+ x = y;
+ i += Dbits;
+ while(i >= 3){+Digout: i -= 3;
+ if(out > buf)
+ out--;
+ else if(x != 0)
+ return -1;
+ *out = '0' + (x & 7);
+ x = y >> Dbits-i;
+ }
+ }
+ if(i > 0)
+ goto Digout;
+
+ while(*out == '0') out++;
+ if(*out == '\0')
+ *--out = '0';
+
+ len -= out-buf;
+ if(out != buf)
+ memmove(buf, out, len);
+ return 0;
+}
+
+int
+mpfmt(Fmt *fmt)
+{+ mpint *b;
+ char *x, *p;
+ int base;
+
+ b = va_arg(fmt->args, mpint*);
+ if(b == nil)
+ return fmtstrcpy(fmt, "*");
+
+ base = fmt->prec;
+ if(base == 0)
+ base = 16; /* default */
+ fmt->flags &= ~FmtPrec;
+ p = mptoa(b, base, nil, 0);
+ if(p == nil)
+ return fmtstrcpy(fmt, "*");
+ else{+ if((fmt->flags & FmtSharp) != 0){+ switch(base){+ case 16:
+ x = "0x";
+ break;
+ case 8:
+ x = "0";
+ break;
+ case 2:
+ x = "0b";
+ break;
+ default:
+ x = "";
+ }
+ if(*p == '-')
+ fmtprint(fmt, "-%s%s", x, p + 1);
+ else
+ fmtprint(fmt, "%s%s", x, p);
+ }
+ else
+ fmtstrcpy(fmt, p);
+ free(p);
+ return 0;
+ }
+}
+
+char*
+mptoa(mpint *b, int base, char *buf, int len)
+{+ char *out;
+ int rv, alloced;
+
+ if(base == 0)
+ base = 16; /* default */
+ alloced = 0;
+ if(buf == nil){+ /* rv <= log₂(base) */
+ for(rv=1; (base >> rv) > 1; rv++)
+ ;
+ len = 10 + (b->top*Dbits / rv);
+ buf = malloc(len);
+ if(buf == nil)
+ return nil;
+ alloced = 1;
+ }
+
+ if(len < 2)
+ return nil;
+
+ out = buf;
+ if(b->sign < 0){+ *out++ = '-';
+ len--;
+ }
+ switch(base){+ case 64:
+ rv = toencx(b, out, len, enc64);
+ break;
+ case 32:
+ rv = toencx(b, out, len, enc32);
+ break;
+ case 16:
+ rv = topow2(b, out, len, 4);
+ break;
+ case 10:
+ rv = to10(b, out, len);
+ break;
+ case 8:
+ rv = to8(b, out, len);
+ break;
+ case 4:
+ rv = topow2(b, out, len, 2);
+ break;
+ case 2:
+ rv = topow2(b, out, len, 1);
+ break;
+ default:
+ abort();
+ return nil;
+ }
+ if(rv < 0){+ if(alloced)
+ free(buf);
+ return nil;
+ }
+ return buf;
+}
--- /dev/null
+++ b/libmp/mpinvert.c
@@ -1,0 +1,17 @@
+#include "os.h"
+#include <mp.h>
+
+// use extended gcd to find the multiplicative inverse
+// res = b**-1 mod m
+void
+mpinvert(mpint *b, mpint *m, mpint *res)
+{+ mpint *v;
+
+ v = mpnew(0);
+ mpextendedgcd(b, m, v, res, nil);
+ if(mpcmp(v, mpone) != 0)
+ abort();
+ mpfree(v);
+ mpmod(res, m, res);
+}
--- /dev/null
+++ b/libmp/mpleft.c
@@ -1,0 +1,51 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// res = b << shift
+void
+mpleft(mpint *b, int shift, mpint *res)
+{+ int d, l, r, i, otop;
+ mpdigit this, last;
+
+ res->sign = b->sign;
+ if(b->top==0){+ res->top = 0;
+ return;
+ }
+
+ // a zero or negative left shift is a right shift
+ if(shift <= 0){+ mpright(b, -shift, res);
+ return;
+ }
+
+ // b and res may be the same so remember the old top
+ otop = b->top;
+
+ // shift
+ mpbits(res, otop*Dbits + shift); // overkill
+ res->top = DIGITS(otop*Dbits + shift);
+ d = shift/Dbits;
+ l = shift - d*Dbits;
+ r = Dbits - l;
+
+ if(l == 0){+ for(i = otop-1; i >= 0; i--)
+ res->p[i+d] = b->p[i];
+ } else {+ last = 0;
+ for(i = otop-1; i >= 0; i--) {+ this = b->p[i];
+ res->p[i+d+1] = (last<<l) | (this>>r);
+ last = this;
+ }
+ res->p[d] = last<<l;
+ }
+ for(i = 0; i < d; i++)
+ res->p[i] = 0;
+
+ res->flags |= b->flags & MPtimesafe;
+ mpnorm(res);
+}
--- /dev/null
+++ b/libmp/mplogic.c
@@ -1,0 +1,212 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+/*
+ mplogic calculates b1|b2 subject to the
+ following flag bits (fl)
+
+ bit 0: subtract 1 from b1
+ bit 1: invert b1
+ bit 2: subtract 1 from b2
+ bit 3: invert b2
+ bit 4: add 1 to output
+ bit 5: invert output
+
+ it inverts appropriate bits automatically
+ depending on the signs of the inputs
+*/
+
+static void
+mplogic(mpint *b1, mpint *b2, mpint *sum, int fl)
+{+ mpint *t;
+ mpdigit *dp1, *dp2, *dpo, d1, d2, d;
+ int c1, c2, co;
+ int i;
+
+ assert(((b1->flags | b2->flags | sum->flags) & MPtimesafe) == 0);
+ if(b1->sign < 0) fl ^= 0x03;
+ if(b2->sign < 0) fl ^= 0x0c;
+ sum->sign = (int)(((fl|fl>>2)^fl>>4)<<30)>>31|1;
+ if(sum->sign < 0) fl ^= 0x30;
+ if(b2->top > b1->top){+ t = b1;
+ b1 = b2;
+ b2 = t;
+ fl = fl >> 2 & 0x03 | fl << 2 & 0x0c | fl & 0x30;
+ }
+ mpbits(sum, b1->top*Dbits+1);
+ dp1 = b1->p;
+ dp2 = b2->p;
+ dpo = sum->p;
+ c1 = fl & 1;
+ c2 = fl >> 2 & 1;
+ co = fl >> 4 & 1;
+ for(i = 0; i < b1->top; i++){+ d1 = dp1[i] - c1;
+ if(i < b2->top)
+ d2 = dp2[i] - c2;
+ else
+ d2 = 0;
+ if(d1 != (mpdigit)-1) c1 = 0;
+ if(d2 != (mpdigit)-1) c2 = 0;
+ if((fl & 2) != 0) d1 ^= -1;
+ if((fl & 8) != 0) d2 ^= -1;
+ d = d1 | d2;
+ if((fl & 32) != 0) d ^= -1;
+ d += co;
+ if(d != 0) co = 0;
+ dpo[i] = d;
+ }
+ sum->top = i;
+ if(co)
+ dpo[sum->top++] = co;
+ mpnorm(sum);
+}
+
+void
+mpor(mpint *b1, mpint *b2, mpint *sum)
+{+ mplogic(b1, b2, sum, 0);
+}
+
+void
+mpand(mpint *b1, mpint *b2, mpint *sum)
+{+ mplogic(b1, b2, sum, 0x2a);
+}
+
+void
+mpbic(mpint *b1, mpint *b2, mpint *sum)
+{+ mplogic(b1, b2, sum, 0x22);
+}
+
+void
+mpnot(mpint *b, mpint *r)
+{+ mpadd(b, mpone, r);
+ if(r->top != 0)
+ r->sign ^= -2;
+}
+
+void
+mpxor(mpint *b1, mpint *b2, mpint *sum)
+{+ mpint *t;
+ mpdigit *dp1, *dp2, *dpo, d1, d2, d;
+ int c1, c2, co;
+ int i, fl;
+
+ assert(((b1->flags | b2->flags | sum->flags) & MPtimesafe) == 0);
+ if(b2->top > b1->top){+ t = b1;
+ b1 = b2;
+ b2 = t;
+ }
+ fl = (b1->sign & 10) ^ (b2->sign & 12);
+ sum->sign = (int)(fl << 28) >> 31 | 1;
+ mpbits(sum, b1->top*Dbits+1);
+ dp1 = b1->p;
+ dp2 = b2->p;
+ dpo = sum->p;
+ c1 = fl >> 1 & 1;
+ c2 = fl >> 2 & 1;
+ co = fl >> 3 & 1;
+ for(i = 0; i < b1->top; i++){+ d1 = dp1[i] - c1;
+ if(i < b2->top)
+ d2 = dp2[i] - c2;
+ else
+ d2 = 0;
+ if(d1 != (mpdigit)-1) c1 = 0;
+ if(d2 != (mpdigit)-1) c2 = 0;
+ d = d1 ^ d2;
+ d += co;
+ if(d != 0) co = 0;
+ dpo[i] = d;
+ }
+ sum->top = i;
+ if(co)
+ dpo[sum->top++] = co;
+ mpnorm(sum);
+}
+
+void
+mptrunc(mpint *b, int n, mpint *r)
+{+ int d, m, i, c;
+
+ assert(((b->flags | r->flags) & MPtimesafe) == 0);
+ mpbits(r, n);
+ r->top = DIGITS(n);
+ d = n / Dbits;
+ m = n % Dbits;
+ if(b->sign == -1){+ c = 1;
+ for(i = 0; i < r->top; i++){+ if(i < b->top)
+ r->p[i] = ~(b->p[i] - c);
+ else
+ r->p[i] = -1;
+ if(r->p[i] != 0)
+ c = 0;
+ }
+ if(m != 0)
+ r->p[d] &= (1<<m) - 1;
+ }else if(b->sign == 1){+ if(d >= b->top){+ mpassign(b, r);
+ mpnorm(r);
+ return;
+ }
+ if(b != r)
+ for(i = 0; i < d; i++)
+ r->p[i] = b->p[i];
+ if(m != 0)
+ r->p[d] = b->p[d] & (1<<m)-1;
+ }
+ r->sign = 1;
+ mpnorm(r);
+}
+
+void
+mpxtend(mpint *b, int n, mpint *r)
+{+ int d, m, c, i;
+
+ d = (n - 1) / Dbits;
+ m = (n - 1) % Dbits;
+ if(d >= b->top){+ mpassign(b, r);
+ return;
+ }
+ mptrunc(b, n, r);
+ mpbits(r, n);
+ if((r->p[d] & 1<<m) == 0){+ mpnorm(r);
+ return;
+ }
+ r->p[d] |= -(1<<m);
+ r->sign = -1;
+ c = 1;
+ for(i = 0; i < r->top; i++){+ r->p[i] = ~(r->p[i] - c);
+ if(r->p[i] != 0)
+ c = 0;
+ }
+ mpnorm(r);
+}
+
+void
+mpasr(mpint *b, int n, mpint *r)
+{+ if(b->sign > 0 || n <= 0){+ mpright(b, n, r);
+ return;
+ }
+ mpadd(b, mpone, r);
+ mpright(r, n, r);
+ mpsub(r, mpone, r);
+}
--- /dev/null
+++ b/libmp/mpmod.c
@@ -1,0 +1,20 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+void
+mpmod(mpint *x, mpint *n, mpint *r)
+{+ int sign;
+ mpint *ns;
+
+ sign = x->sign;
+ ns = sign < 0 && n == r ? mpcopy(n) : n;
+ if((n->flags & MPfield) == 0
+ || ((Mfield*)n)->reduce((Mfield*)n, x, r) != 0)
+ mpdiv(x, n, nil, r);
+ if(sign < 0){+ mpmagsub(ns, r, r);
+ if(ns != n) mpfree(ns);
+ }
+}
--- /dev/null
+++ b/libmp/mpmodop.c
@@ -1,0 +1,95 @@
+#include "os.h"
+#include <mp.h>
+
+/* operands need to have m->top+1 digits of space and satisfy 0 ≤ a ≤ m-1 */
+static mpint*
+modarg(mpint *a, mpint *m)
+{+ if(a->size <= m->top || a->sign < 0 || mpmagcmp(a, m) >= 0){+ a = mpcopy(a);
+ mpmod(a, m, a);
+ mpbits(a, Dbits*(m->top+1));
+ a->top = m->top;
+ } else if(a->top < m->top){+ memset(&a->p[a->top], 0, (m->top - a->top)*Dbytes);
+ }
+ return a;
+}
+
+void
+mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
+{+ mpint *a, *b;
+ mpdigit d;
+ int i, j;
+
+ a = modarg(b1, m);
+ b = modarg(b2, m);
+
+ sum->flags |= (a->flags | b->flags) & MPtimesafe;
+ mpbits(sum, Dbits*2*(m->top+1));
+
+ mpvecadd(a->p, m->top, b->p, m->top, sum->p);
+ mpvecsub(sum->p, m->top+1, m->p, m->top, sum->p+m->top+1);
+
+ d = sum->p[2*m->top+1];
+ for(i = 0, j = m->top+1; i < m->top; i++, j++)
+ sum->p[i] = (sum->p[i] & d) | (sum->p[j] & ~d);
+
+ sum->top = m->top;
+ sum->sign = 1;
+ mpnorm(sum);
+
+ if(a != b1)
+ mpfree(a);
+ if(b != b2)
+ mpfree(b);
+}
+
+void
+mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
+{+ mpint *a, *b;
+ mpdigit d;
+ int i, j;
+
+ a = modarg(b1, m);
+ b = modarg(b2, m);
+
+ diff->flags |= (a->flags | b->flags) & MPtimesafe;
+ mpbits(diff, Dbits*2*(m->top+1));
+
+ a->p[m->top] = 0;
+ mpvecsub(a->p, m->top+1, b->p, m->top, diff->p);
+ mpvecadd(diff->p, m->top, m->p, m->top, diff->p+m->top+1);
+
+ d = ~diff->p[m->top];
+ for(i = 0, j = m->top+1; i < m->top; i++, j++)
+ diff->p[i] = (diff->p[i] & d) | (diff->p[j] & ~d);
+
+ diff->top = m->top;
+ diff->sign = 1;
+ mpnorm(diff);
+
+ if(a != b1)
+ mpfree(a);
+ if(b != b2)
+ mpfree(b);
+}
+
+void
+mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
+{+ mpint *a, *b;
+
+ a = modarg(b1, m);
+ b = modarg(b2, m);
+
+ mpmul(a, b, prod);
+ mpmod(prod, m, prod);
+
+ if(a != b1)
+ mpfree(a);
+ if(b != b2)
+ mpfree(b);
+}
--- /dev/null
+++ b/libmp/mpmul.c
@@ -1,0 +1,176 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+//
+// from knuth's 1969 seminumberical algorithms, pp 233-235 and pp 258-260
+//
+// mpvecmul is an assembly language routine that performs the inner
+// loop.
+//
+// the karatsuba trade off is set empiricly by measuring the algs on
+// a 400 MHz Pentium II.
+//
+
+// karatsuba like (see knuth pg 258)
+// prereq: p is already zeroed
+static void
+mpkaratsuba(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
+{+ mpdigit *t, *u0, *u1, *v0, *v1, *u0v0, *u1v1, *res, *diffprod;
+ int u0len, u1len, v0len, v1len, reslen;
+ int sign, n;
+
+ // divide each piece in half
+ n = alen/2;
+ if(alen&1)
+ n++;
+ u0len = n;
+ u1len = alen-n;
+ if(blen > n){+ v0len = n;
+ v1len = blen-n;
+ } else {+ v0len = blen;
+ v1len = 0;
+ }
+ u0 = a;
+ u1 = a + u0len;
+ v0 = b;
+ v1 = b + v0len;
+
+ // room for the partial products
+ t = mallocz(Dbytes*5*(2*n+1), 1);
+ if(t == nil)
+ sysfatal("mpkaratsuba: %r");+ u0v0 = t;
+ u1v1 = t + (2*n+1);
+ diffprod = t + 2*(2*n+1);
+ res = t + 3*(2*n+1);
+ reslen = 4*n+1;
+
+ // t[0] = (u1-u0)
+ sign = 1;
+ if(mpveccmp(u1, u1len, u0, u0len) < 0){+ sign = -1;
+ mpvecsub(u0, u0len, u1, u1len, u0v0);
+ } else
+ mpvecsub(u1, u1len, u0, u1len, u0v0);
+
+ // t[1] = (v0-v1)
+ if(mpveccmp(v0, v0len, v1, v1len) < 0){+ sign *= -1;
+ mpvecsub(v1, v1len, v0, v1len, u1v1);
+ } else
+ mpvecsub(v0, v0len, v1, v1len, u1v1);
+
+ // t[4:5] = (u1-u0)*(v0-v1)
+ mpvecmul(u0v0, u0len, u1v1, v0len, diffprod);
+
+ // t[0:1] = u1*v1
+ memset(t, 0, 2*(2*n+1)*Dbytes);
+ if(v1len > 0)
+ mpvecmul(u1, u1len, v1, v1len, u1v1);
+
+ // t[2:3] = u0v0
+ mpvecmul(u0, u0len, v0, v0len, u0v0);
+
+ // res = u0*v0<<n + u0*v0
+ mpvecadd(res, reslen, u0v0, u0len+v0len, res);
+ mpvecadd(res+n, reslen-n, u0v0, u0len+v0len, res+n);
+
+ // res += u1*v1<<n + u1*v1<<2*n
+ if(v1len > 0){+ mpvecadd(res+n, reslen-n, u1v1, u1len+v1len, res+n);
+ mpvecadd(res+2*n, reslen-2*n, u1v1, u1len+v1len, res+2*n);
+ }
+
+ // res += (u1-u0)*(v0-v1)<<n
+ if(sign < 0)
+ mpvecsub(res+n, reslen-n, diffprod, u0len+v0len, res+n);
+ else
+ mpvecadd(res+n, reslen-n, diffprod, u0len+v0len, res+n);
+ memmove(p, res, (alen+blen)*Dbytes);
+
+ free(t);
+}
+
+#define KARATSUBAMIN 32
+
+void
+mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
+{+ int i;
+ mpdigit d;
+ mpdigit *t;
+
+ // both mpvecdigmuladd and karatsuba are fastest when a is the longer vector
+ if(alen < blen){+ i = alen;
+ alen = blen;
+ blen = i;
+ t = a;
+ a = b;
+ b = t;
+ }
+
+ if(alen >= KARATSUBAMIN && blen > 1){+ // O(n^1.585)
+ mpkaratsuba(a, alen, b, blen, p);
+ } else {+ // O(n^2)
+ for(i = 0; i < blen; i++){+ d = b[i];
+ if(d != 0)
+ mpvecdigmuladd(a, alen, d, &p[i]);
+ }
+ }
+}
+
+void
+mpvectsmul(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *p)
+{+ int i;
+ mpdigit *t;
+
+ if(alen < blen){+ i = alen;
+ alen = blen;
+ blen = i;
+ t = a;
+ a = b;
+ b = t;
+ }
+ if(blen == 0)
+ return;
+ for(i = 0; i < blen; i++)
+ mpvecdigmuladd(a, alen, b[i], &p[i]);
+}
+
+void
+mpmul(mpint *b1, mpint *b2, mpint *prod)
+{+ mpint *oprod;
+
+ oprod = prod;
+ if(prod == b1 || prod == b2){+ prod = mpnew(0);
+ prod->flags = oprod->flags;
+ }
+ prod->flags |= (b1->flags | b2->flags) & MPtimesafe;
+
+ prod->top = 0;
+ mpbits(prod, (b1->top+b2->top+1)*Dbits);
+ if(prod->flags & MPtimesafe)
+ mpvectsmul(b1->p, b1->top, b2->p, b2->top, prod->p);
+ else
+ mpvecmul(b1->p, b1->top, b2->p, b2->top, prod->p);
+ prod->top = b1->top+b2->top+1;
+ prod->sign = b1->sign*b2->sign;
+ mpnorm(prod);
+
+ if(oprod != prod){+ mpassign(prod, oprod);
+ mpfree(prod);
+ }
+}
--- /dev/null
+++ b/libmp/mpnrand.c
@@ -1,0 +1,23 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+/* return uniform random [0..n-1] */
+mpint*
+mpnrand(mpint *n, void (*gen)(uchar*, int), mpint *b)
+{+ int bits;
+
+ bits = mpsignif(n);
+ if(bits == 0)
+ abort();
+ if(b == nil){+ b = mpnew(bits);
+ setmalloctag(b, getcallerpc(&n));
+ }
+ do {+ mprand(bits, gen, b);
+ } while(mpmagcmp(b, n) >= 0);
+
+ return b;
+}
--- /dev/null
+++ b/libmp/mprand.c
@@ -1,0 +1,25 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+mpint*
+mprand(int bits, void (*gen)(uchar*, int), mpint *b)
+{+ mpdigit mask;
+
+ if(b == nil){+ b = mpnew(bits);
+ setmalloctag(b, getcallerpc(&bits));
+ }else
+ mpbits(b, bits);
+
+ b->sign = 1;
+ b->top = DIGITS(bits);
+ (*gen)((uchar*)b->p, b->top*Dbytes);
+
+ mask = ((mpdigit)1 << (bits%Dbits))-1;
+ if(mask != 0)
+ b->p[b->top-1] &= mask;
+
+ return mpnorm(b);
+}
--- /dev/null
+++ b/libmp/mpright.c
@@ -1,0 +1,57 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// res = b >> shift
+void
+mpright(mpint *b, int shift, mpint *res)
+{+ int d, l, r, i;
+ mpdigit this, last;
+
+ res->sign = b->sign;
+ if(b->top==0){+ res->top = 0;
+ return;
+ }
+
+ // a negative right shift is a left shift
+ if(shift < 0){+ mpleft(b, -shift, res);
+ return;
+ }
+
+ if(res != b)
+ mpbits(res, b->top*Dbits - shift);
+ else if(shift == 0)
+ return;
+
+ d = shift/Dbits;
+ r = shift - d*Dbits;
+ l = Dbits - r;
+
+ // shift all the bits out == zero
+ if(d>=b->top){+ res->sign = 1;
+ res->top = 0;
+ return;
+ }
+
+ // special case digit shifts
+ if(r == 0){+ for(i = 0; i < b->top-d; i++)
+ res->p[i] = b->p[i+d];
+ } else {+ last = b->p[d];
+ for(i = 0; i < b->top-d-1; i++){+ this = b->p[i+d+1];
+ res->p[i] = (this<<l) | (last>>r);
+ last = this;
+ }
+ res->p[i++] = last>>r;
+ }
+
+ res->top = i;
+ res->flags |= b->flags & MPtimesafe;
+ mpnorm(res);
+}
--- /dev/null
+++ b/libmp/mpsel.c
@@ -1,0 +1,42 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// res = s != 0 ? b1 : b2
+void
+mpsel(int s, mpint *b1, mpint *b2, mpint *res)
+{+ mpdigit d;
+ int n, m, i;
+
+ res->flags |= (b1->flags | b2->flags) & MPtimesafe;
+ if((res->flags & MPtimesafe) == 0){+ mpassign(s ? b1 : b2, res);
+ return;
+ }
+ res->flags &= ~MPnorm;
+
+ n = b1->top;
+ m = b2->top;
+ mpbits(res, Dbits*(n >= m ? n : m));
+ res->top = n >= m ? n : m;
+
+ s = (-s^s|s)>>(sizeof(s)*8-1);
+ res->sign = (b1->sign & s) | (b2->sign & ~s);
+
+ d = -((mpdigit)s & 1);
+
+ i = 0;
+ while(i < n && i < m){+ res->p[i] = (b1->p[i] & d) | (b2->p[i] & ~d);
+ i++;
+ }
+ while(i < n){+ res->p[i] = b1->p[i] & d;
+ i++;
+ }
+ while(i < m){+ res->p[i] = b2->p[i] & ~d;
+ i++;
+ }
+}
--- /dev/null
+++ b/libmp/mpsub.c
@@ -1,0 +1,56 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// diff = abs(b1) - abs(b2), i.e., subtract the magnitudes
+void
+mpmagsub(mpint *b1, mpint *b2, mpint *diff)
+{+ int n, m, sign;
+ mpint *t;
+
+ // get the sizes right
+ if(mpmagcmp(b1, b2) < 0){+ assert(((b1->flags | b2->flags | diff->flags) & MPtimesafe) == 0);
+ sign = -1;
+ t = b1;
+ b1 = b2;
+ b2 = t;
+ } else {+ diff->flags |= (b1->flags | b2->flags) & MPtimesafe;
+ sign = 1;
+ }
+ n = b1->top;
+ m = b2->top;
+ if(m == 0){+ mpassign(b1, diff);
+ diff->sign = sign;
+ return;
+ }
+ mpbits(diff, n*Dbits);
+
+ mpvecsub(b1->p, n, b2->p, m, diff->p);
+ diff->sign = sign;
+ diff->top = n;
+ mpnorm(diff);
+}
+
+// diff = b1 - b2
+void
+mpsub(mpint *b1, mpint *b2, mpint *diff)
+{+ int sign;
+
+ if(b1->sign != b2->sign){+ assert(((b1->flags | b2->flags | diff->flags) & MPtimesafe) == 0);
+ sign = b1->sign;
+ mpmagadd(b1, b2, diff);
+ diff->sign = sign;
+ return;
+ }
+
+ sign = b1->sign;
+ mpmagsub(b1, b2, diff);
+ if(diff->top != 0)
+ diff->sign *= sign;
+}
--- /dev/null
+++ b/libmp/mptobe.c
@@ -1,0 +1,32 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// convert an mpint into a big endian byte array (most significant byte first; left adjusted)
+// return number of bytes converted
+// if p == nil, allocate and result array
+int
+mptobe(mpint *b, uchar *p, uint n, uchar **pp)
+{+ int m;
+
+ m = (mpsignif(b)+7)/8;
+ if(m == 0)
+ m++;
+ if(p == nil){+ n = m;
+ p = malloc(n);
+ if(p == nil)
+ sysfatal("mptobe: %r");+ setmalloctag(p, getcallerpc(&b));
+ } else {+ if(n < m)
+ return -1;
+ if(n > m)
+ memset(p+m, 0, n-m);
+ }
+ if(pp != nil)
+ *pp = p;
+ mptober(b, p, m);
+ return m;
+}
--- /dev/null
+++ b/libmp/mptober.c
@@ -1,0 +1,34 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+void
+mptober(mpint *b, uchar *p, int n)
+{+ int i, j, m;
+ mpdigit x;
+
+ memset(p, 0, n);
+
+ p += n;
+ m = b->top*Dbytes;
+ if(m < n)
+ n = m;
+
+ i = 0;
+ while(n >= Dbytes){+ n -= Dbytes;
+ x = b->p[i++];
+ for(j = 0; j < Dbytes; j++){+ *--p = x;
+ x >>= 8;
+ }
+ }
+ if(n > 0){+ x = b->p[i];
+ for(j = 0; j < n; j++){+ *--p = x;
+ x >>= 8;
+ }
+ }
+}
--- /dev/null
+++ b/libmp/mptoi.c
@@ -1,0 +1,44 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+/*
+ * this code assumes that mpdigit is at least as
+ * big as an int.
+ */
+
+mpint*
+itomp(int i, mpint *b)
+{+ if(b == nil){+ b = mpnew(0);
+ setmalloctag(b, getcallerpc(&i));
+ }
+ b->sign = (i >> (sizeof(i)*8 - 1)) | 1;
+ i *= b->sign;
+ *b->p = i;
+ b->top = 1;
+ return mpnorm(b);
+}
+
+int
+mptoi(mpint *b)
+{+ uint x;
+
+ if(b->top==0)
+ return 0;
+ x = *b->p;
+ if(b->sign > 0){+ if(b->top > 1 || (x > MAXINT))
+ x = (int)MAXINT;
+ else
+ x = (int)x;
+ } else {+ if(b->top > 1 || x > MAXINT+1)
+ x = (int)MININT;
+ else
+ x = -(int)x;
+ }
+ return x;
+}
--- /dev/null
+++ b/libmp/mptole.c
@@ -1,0 +1,28 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// convert an mpint into a little endian byte array (least significant byte first)
+// return number of bytes converted
+// if p == nil, allocate and result array
+int
+mptole(mpint *b, uchar *p, uint n, uchar **pp)
+{+ int m;
+
+ m = (mpsignif(b)+7)/8;
+ if(m == 0)
+ m++;
+ if(p == nil){+ n = m;
+ p = malloc(n);
+ if(p == nil)
+ sysfatal("mptole: %r");+ setmalloctag(p, getcallerpc(&b));
+ } else if(n < m)
+ return -1;
+ if(pp != nil)
+ *pp = p;
+ mptolel(b, p, n);
+ return m;
+}
--- /dev/null
+++ b/libmp/mptolel.c
@@ -1,0 +1,33 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+void
+mptolel(mpint *b, uchar *p, int n)
+{+ int i, j, m;
+ mpdigit x;
+
+ memset(p, 0, n);
+
+ m = b->top*Dbytes;
+ if(m < n)
+ n = m;
+
+ i = 0;
+ while(n >= Dbytes){+ n -= Dbytes;
+ x = b->p[i++];
+ for(j = 0; j < Dbytes; j++){+ *p++ = x;
+ x >>= 8;
+ }
+ }
+ if(n > 0){+ x = b->p[i];
+ for(j = 0; j < n; j++){+ *p++ = x;
+ x >>= 8;
+ }
+ }
+}
--- /dev/null
+++ b/libmp/mptoui.c
@@ -1,0 +1,34 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+/*
+ * this code assumes that mpdigit is at least as
+ * big as an int.
+ */
+
+mpint*
+uitomp(uint i, mpint *b)
+{+ if(b == nil){+ b = mpnew(0);
+ setmalloctag(b, getcallerpc(&i));
+ }
+ *b->p = i;
+ b->top = 1;
+ b->sign = 1;
+ return mpnorm(b);
+}
+
+uint
+mptoui(mpint *b)
+{+ uint x;
+
+ x = *b->p;
+ if(b->sign < 0)
+ x = 0;
+ else if(b->top > 1 || (sizeof(mpdigit) > sizeof(uint) && x > MAXUINT))
+ x = MAXUINT;
+ return x;
+}
--- /dev/null
+++ b/libmp/mptouv.c
@@ -1,0 +1,47 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+#define VLDIGITS (sizeof(vlong)/sizeof(mpdigit))
+
+/*
+ * this code assumes that a vlong is an integral number of
+ * mpdigits long.
+ */
+mpint*
+uvtomp(uvlong v, mpint *b)
+{+ int s;
+
+ if(b == nil){+ b = mpnew(VLDIGITS*Dbits);
+ setmalloctag(b, getcallerpc(&v));
+ }else
+ mpbits(b, VLDIGITS*Dbits);
+ b->sign = 1;
+ for(s = 0; s < VLDIGITS; s++){+ b->p[s] = v;
+ v >>= sizeof(mpdigit)*8;
+ }
+ b->top = s;
+ return mpnorm(b);
+}
+
+uvlong
+mptouv(mpint *b)
+{+ uvlong v;
+ int s;
+
+ if(b->top == 0 || b->sign < 0)
+ return 0LL;
+
+ if(b->top > VLDIGITS)
+ return -1LL;
+
+ v = 0ULL;
+ for(s = 0; s < b->top; s++)
+ v |= (uvlong)b->p[s]<<(s*sizeof(mpdigit)*8);
+
+ return v;
+}
--- /dev/null
+++ b/libmp/mptov.c
@@ -1,0 +1,63 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+#define VLDIGITS (sizeof(vlong)/sizeof(mpdigit))
+
+/*
+ * this code assumes that a vlong is an integral number of
+ * mpdigits long.
+ */
+mpint*
+vtomp(vlong v, mpint *b)
+{+ int s;
+ uvlong uv;
+
+ if(b == nil){+ b = mpnew(VLDIGITS*Dbits);
+ setmalloctag(b, getcallerpc(&v));
+ }else
+ mpbits(b, VLDIGITS*Dbits);
+ b->sign = (v >> (sizeof(v)*8 - 1)) | 1;
+ uv = v * b->sign;
+ for(s = 0; s < VLDIGITS; s++){+ b->p[s] = uv;
+ uv >>= sizeof(mpdigit)*8;
+ }
+ b->top = s;
+ return mpnorm(b);
+}
+
+vlong
+mptov(mpint *b)
+{+ uvlong v;
+ int s;
+
+ if(b->top == 0)
+ return 0LL;
+
+ if(b->top > VLDIGITS){+ if(b->sign > 0)
+ return (vlong)MAXVLONG;
+ else
+ return (vlong)MINVLONG;
+ }
+
+ v = 0ULL;
+ for(s = 0; s < b->top; s++)
+ v |= (uvlong)b->p[s]<<(s*sizeof(mpdigit)*8);
+
+ if(b->sign > 0){+ if(v > MAXVLONG)
+ v = MAXVLONG;
+ } else {+ if(v > MINVLONG)
+ v = MINVLONG;
+ else
+ v = -(vlong)v;
+ }
+
+ return (vlong)v;
+}
--- /dev/null
+++ b/libmp/mpvecadd.c
@@ -1,0 +1,35 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// prereq: alen >= blen, sum has at least blen+1 digits
+void
+mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
+{+ int i, carry;
+ mpdigit x, y;
+
+ carry = 0;
+ for(i = 0; i < blen; i++){+ x = *a++;
+ y = *b++;
+ x += carry;
+ if(x < carry)
+ carry = 1;
+ else
+ carry = 0;
+ x += y;
+ if(x < y)
+ carry++;
+ *sum++ = x;
+ }
+ for(; i < alen; i++){+ x = *a++ + carry;
+ if(x < carry)
+ carry = 1;
+ else
+ carry = 0;
+ *sum++ = x;
+ }
+ *sum = carry;
+}
--- /dev/null
+++ b/libmp/mpveccmp.c
@@ -1,0 +1,27 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+int
+mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
+{+ mpdigit x;
+
+ while(alen > blen)
+ if(a[--alen] != 0)
+ return 1;
+ while(blen > alen)
+ if(b[--blen] != 0)
+ return -1;
+ while(alen > 0){+ --alen;
+ x = a[alen] - b[alen];
+ if(x == 0)
+ continue;
+ if(x > a[alen])
+ return -1;
+ else
+ return 1;
+ }
+ return 0;
+}
--- /dev/null
+++ b/libmp/mpvecdigmuladd.c
@@ -1,0 +1,103 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+#define LO(x) ((x) & ((1<<(Dbits/2))-1))
+#define HI(x) ((x) >> (Dbits/2))
+
+static void
+mpdigmul(mpdigit a, mpdigit b, mpdigit *p)
+{+ mpdigit x, ah, al, bh, bl, p1, p2, p3, p4;
+ int carry;
+
+ // half digits
+ ah = HI(a);
+ al = LO(a);
+ bh = HI(b);
+ bl = LO(b);
+
+ // partial products
+ p1 = ah*bl;
+ p2 = bh*al;
+ p3 = bl*al;
+ p4 = ah*bh;
+
+ // p = ((p1+p2)<<(Dbits/2)) + (p4<<Dbits) + p3
+ carry = 0;
+ x = p1<<(Dbits/2);
+ p3 += x;
+ if(p3 < x)
+ carry++;
+ x = p2<<(Dbits/2);
+ p3 += x;
+ if(p3 < x)
+ carry++;
+ p4 += carry + HI(p1) + HI(p2); // can't carry out of the high digit
+ p[0] = p3;
+ p[1] = p4;
+}
+
+// prereq: p must have room for n+1 digits
+void
+mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
+{+ int i;
+ mpdigit carry, x, y, part[2];
+
+ carry = 0;
+ part[1] = 0;
+ for(i = 0; i < n; i++){+ x = part[1] + carry;
+ if(x < carry)
+ carry = 1;
+ else
+ carry = 0;
+ y = *p;
+ mpdigmul(*b++, m, part);
+ x += part[0];
+ if(x < part[0])
+ carry++;
+ x += y;
+ if(x < y)
+ carry++;
+ *p++ = x;
+ }
+ *p = part[1] + carry;
+}
+
+// prereq: p must have room for n+1 digits
+int
+mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
+{+ int i;
+ mpdigit x, y, part[2], borrow;
+
+ borrow = 0;
+ part[1] = 0;
+ for(i = 0; i < n; i++){+ x = *p;
+ y = x - borrow;
+ if(y > x)
+ borrow = 1;
+ else
+ borrow = 0;
+ x = part[1];
+ mpdigmul(*b++, m, part);
+ x += part[0];
+ if(x < part[0])
+ borrow++;
+ x = y - x;
+ if(x > y)
+ borrow++;
+ *p++ = x;
+ }
+
+ x = *p;
+ y = x - borrow - part[1];
+ *p = y;
+ if(y > x)
+ return -1;
+ else
+ return 1;
+}
--- /dev/null
+++ b/libmp/mpvecsub.c
@@ -1,0 +1,34 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+// prereq: a >= b, alen >= blen, diff has at least alen digits
+void
+mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
+{+ int i, borrow;
+ mpdigit x, y;
+
+ borrow = 0;
+ for(i = 0; i < blen; i++){+ x = *a++;
+ y = *b++;
+ y += borrow;
+ if(y < borrow)
+ borrow = 1;
+ else
+ borrow = 0;
+ if(x < y)
+ borrow++;
+ *diff++ = x - y;
+ }
+ for(; i < alen; i++){+ x = *a++;
+ y = x - borrow;
+ if(y > x)
+ borrow = 1;
+ else
+ borrow = 0;
+ *diff++ = y;
+ }
+}
--- /dev/null
+++ b/libmp/mpvectscmp.c
@@ -1,0 +1,34 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+int
+mpvectscmp(mpdigit *a, int alen, mpdigit *b, int blen)
+{+ mpdigit x, y, z, v;
+ int m, p;
+
+ if(alen > blen){+ v = 0;
+ while(alen > blen)
+ v |= a[--alen];
+ m = p = (-v^v|v)>>Dbits-1;
+ } else if(blen > alen){+ v = 0;
+ while(blen > alen)
+ v |= b[--blen];
+ m = (-v^v|v)>>Dbits-1;
+ p = m^1;
+ } else
+ m = p = 0;
+ while(alen-- > 0){+ x = a[alen];
+ y = b[alen];
+ z = x - y;
+ x = ~x;
+ v = ((-z^z|z)>>Dbits-1) & ~m;
+ p = ((~(x&y|x&z|y&z)>>Dbits-1) & v) | (p & ~v);
+ m |= v;
+ }
+ return (p-m) | m;
+}
--- /dev/null
+++ b/libmp/os.h
@@ -1,0 +1,3 @@
+#include <u.h>
+#include <libc.h>
+
--- /dev/null
+++ b/libmp/reduce
@@ -1,0 +1,16 @@
+O=$1
+shift
+objtype=$1
+shift
+
+ls -p ../$objtype/*.[cs] >[2]/dev/null | sed 's/..$//' > /tmp/reduce.$pid
+#
+# if empty directory, just return the input files
+#
+if (! ~ $status '|') {+ echo $*
+ rm /tmp/reduce.$pid
+ exit 0
+}
+echo $* | tr ' ' \012 | grep -v -f /tmp/reduce.$pid | tr \012 ' '
+rm /tmp/reduce.$pid
--- /dev/null
+++ b/libmp/strtomp.c
@@ -1,0 +1,206 @@
+#include "os.h"
+#include <mp.h>
+#include "dat.h"
+
+static char*
+frompow2(char *a, mpint *b, int s)
+{+ char *p, *next;
+ mpdigit x;
+ int i;
+
+ i = 1<<s;
+ for(p = a; (dec16chr(*p) & 255) < i; p++)
+ ;
+
+ mpbits(b, (p-a)*s);
+ b->top = 0;
+ next = p;
+
+ while(p > a){+ x = 0;
+ for(i = 0; i < Dbits; i += s){+ if(p <= a)
+ break;
+ x |= dec16chr(*--p)<<i;
+ }
+ b->p[b->top++] = x;
+ }
+ return next;
+}
+
+static char*
+from8(char *a, mpint *b)
+{+ char *p, *next;
+ mpdigit x, y;
+ int i;
+
+ for(p = a; ((*p - '0') & 255) < 8; p++)
+ ;
+
+ mpbits(b, (p-a)*3);
+ b->top = 0;
+ next = p;
+
+ i = 0;
+ x = y = 0;
+ while(p > a){+ y = *--p - '0';
+ x |= y << i;
+ i += 3;
+ if(i >= Dbits){+Digout:
+ i -= Dbits;
+ b->p[b->top++] = x;
+ x = y >> 3-i;
+ }
+ }
+ if(i > 0)
+ goto Digout;
+
+ return next;
+}
+
+static ulong mppow10[] = {+ 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000
+};
+
+static char*
+from10(char *a, mpint *b)
+{+ ulong x, y;
+ mpint *pow, *r;
+ int i;
+
+ pow = mpnew(0);
+ r = mpnew(0);
+
+ b->top = 0;
+ for(;;){+ // do a billion at a time in native arithmetic
+ x = 0;
+ for(i = 0; i < 9; i++){+ y = *a - '0';
+ if(y > 9)
+ break;
+ a++;
+ x *= 10;
+ x += y;
+ }
+ if(i == 0)
+ break;
+
+ // accumulate into mpint
+ uitomp(mppow10[i], pow);
+ uitomp(x, r);
+ mpmul(b, pow, b);
+ mpadd(b, r, b);
+ if(i < 9)
+ break;
+ }
+ mpfree(pow);
+ mpfree(r);
+ return a;
+}
+
+static char*
+fromdecx(char *a, mpint *b, int (*chr)(int), int (*dec)(uchar*, int, char*, int))
+{+ char *buf = a;
+ uchar *p;
+ int n, m;
+
+ b->top = 0;
+ for(; (*chr)(*a) >= 0; a++)
+ ;
+ n = a-buf;
+ if(n > 0){+ p = malloc(n);
+ if(p == nil)
+ sysfatal("malloc: %r");+ m = (*dec)(p, n, buf, n);
+ if(m > 0)
+ betomp(p, m, b);
+ free(p);
+ }
+ return a;
+}
+
+mpint*
+strtomp(char *a, char **pp, int base, mpint *b)
+{+ int sign;
+ char *e;
+
+ if(b == nil){+ b = mpnew(0);
+ setmalloctag(b, getcallerpc(&a));
+ }
+
+ while(*a==' ' || *a=='\t')
+ a++;
+
+ sign = 1;
+ for(;; a++){+ switch(*a){+ case '-':
+ sign *= -1;
+ continue;
+ }
+ break;
+ }
+
+ if(base == 0){+ base = 10;
+ if(a[0] == '0'){+ if(a[1] == 'x' || a[1] == 'X') {+ a += 2;
+ base = 16;
+ } else if(a[1] == 'b' || a[1] == 'B') {+ a += 2;
+ base = 2;
+ } else if(a[1] >= '0' && a[1] <= '7') {+ a++;
+ base = 8;
+ }
+ }
+ }
+
+ switch(base){+ case 2:
+ e = frompow2(a, b, 1);
+ break;
+ case 4:
+ e = frompow2(a, b, 2);
+ break;
+ case 8:
+ e = from8(a, b);
+ break;
+ case 10:
+ e = from10(a, b);
+ break;
+ case 16:
+ e = frompow2(a, b, 4);
+ break;
+ case 32:
+ e = fromdecx(a, b, dec32chr, dec32);
+ break;
+ case 64:
+ e = fromdecx(a, b, dec64chr, dec64);
+ break;
+ default:
+ abort();
+ return nil;
+ }
+
+ if(pp != nil)
+ *pp = e;
+
+ // if no characters parsed, there wasn't a number to convert
+ if(e == a)
+ return nil;
+
+ b->sign = sign;
+ return mpnorm(b);
+}
--- /dev/null
+++ b/pc.1
@@ -1,0 +1,167 @@
+.TH PC 1
+.SH NAME
+pc \- programmer's calculator
+.SH SYNOPSIS
+.B pc
+[
+.B -n
+]
+.SH DESCRIPTION
+.I Pc
+is an arbitrary precision integer calculator with a special emphasis on supporting two's complement bit operations and working with different number bases.
+.PP
+.I Pc
+reads input statements which are either expressions or control statements.
+Multiple statements in one line can be separated by semicolons.
+.I Pc
+prints the value of all expressions that are not terminated by a semicolon.
+.PP
+.I Pc
+can be run non-interactively by using the
+.B -n
+switch. In this case no input prompt is printed.
+.PP
+Expressions can use the C-like operators
+.TP
+.B + - * ** \fR(exponentiation\fR)
+.TP
+.B / % \fR(Euclidean division, by default\fR)
+.TP
+.B "& | ^ ~ ! << >>"
+.TP
+.B "&& || \fR(returning the second argument, if appropriate)"
+.TP
+.B < >= < <= == !=
+.PP
+The \fB$\fR operator performs sign extension. \fIn\fB$\fIx\fR truncates \fIx\fR to \fIn\fR bits and sign extends.
+If \fIn\fR is omitted, it is inferred from the highest set bit (the result is always ≤ 0 in this case).
+.PP
+Variables can be defined using
+.BR = .
+The builtin variable
+.B @
+always refers to the last printed result.
+.PP
+Numbers can use the prefixes
+.B 0b
+(binary),
+.B 0
+(octal),
+.B 0d
+(decimal) and
+.B 0x
+(hexadecimal).
+.B _
+in numbers can be added for readability and is ignored.
+.SS Builtin functions
+.TF \fIcat(a0,n0,...,aN,nN)
+.TP
+.I bin(n)
+Display \fIn\fR in binary.
+.TP
+.I oct(n)
+Display \fIn\fR in octal.
+.TP
+.I dec(n)
+Display \fIn\fR in decimal.
+.TP
+.I hex(n)
+Display \fIn\fR in hexadecimal.
+.TP
+.I pb(n, b)
+Display \fIn\fR in base \fIb\fR (currently must be one of 0, 2, 8, 10, 16; 0 uses the defined output base).
+.TP
+.I abs(n)
+Absolute value of \fIn\fR.
+.TP
+.I round(n,m)
+\fIn\fR rounded to the nearest multiple of \fIm\fR.
+Numbers exactly halfway between are rounded to the next even multiple.
+.TP
+.I floor(n,m)
+\fIn\fR rounded down to the next multiple of \fIm\fR.
+.TP
+.I ceil(n,m)
+\fIn\fR rounded up to the next multiple of \fIm\fR.
+.TP
+.I trunc(n,m)
+\fIn\fR truncated to \fIm\fR bits.
+.TP
+.I xtend(n,m)
+\fIn\fR truncated to \fIm\fR bits, with the highest bit interpreted as a sign bit.
+.TP
+.I rev(n,m)
+\fIn\fR truncated to \fIm\fR bits, with the order of bits reversed.
+.TP
+.I ubits(n)
+The minimum number of bits required to represent \fIn\fR as an unsigned number.
+.TP
+.I sbits(n)
+The minimum number of bits required to represent \fIn\fR as an signed number.
+.TP
+.I nsa(n)
+The number of bits set in \fIn\fR.
+.TP
+.I cat(a\d\s70\s0\u,n\d\s70\s0\u,...,a\d\s7N\s0\u,n\d\s7N\s0\u)
+Truncate each of the \fIa\d\s7i\s0\u\fR arguments to \fIn\d\s7i\s0\u\fR bits and concatenate their binary representation.
+.TP
+.I gcd(n,m)
+The greatest common divisor of \fIn\fR and \fIm\fR.
+.TP
+.I clog(a,b)
+The ceiling of the logarithm of \fIa\fR with respect to base \fIb\fR. \fIb\fR can be omitted, in which case it defaults to 2.
+.TP
+.I minv(n,m)
+The inverse of \fIn\fR mod \fIm\fR.
+.TP
+.I rand(n)
+A random number satisfying 0 ≤ \fIrand(n)\fR < \fIn\fR.
+.SS Control statements
+.PP
+Control statements are always evaluated with default input base 10.
+.TP
+\fL_\fR \fIn\fR
+If \fIn\fR ≠ 0, insert
+.B _
+in all printed numbers, every
+.I n
+digits.
+.TP
+\fL<\fR \fIn\fR
+Set the default input base to \fIn\fR (default 10).
+The input base can always be overriden by the base prefixes defined above.
+.TP
+\fL>\fR \fIn\fR
+Set the output base to \fIn\fR.
+If \fIn\fR = 0 (default), print each number in the base it was input in.
+.TP
+\fL/\fR 0
+Use Euclidean division (default).
+\fIa\fR / \fIb\fR is rounded towards ±∞ (opposite sign as \fIb\fR).
+\fIa\fR % \fIb\fR is always non-negative.
+.TP
+\fL/\fR 1
+Use truncating division (same as C).
+\fIa\fR / \fIb\fR is rounded towards zero.
+\fIa\fR % \fIb\fR can be negative.
+.TP
+\fL\'\fR 1
+Enable numbering bits (disable with 0).
+If the base is a power of two, print the number of the corresponding bit above each digit.
+.SH SOURCE
+.B /sys/src/cmd/pc.y
+.SH "SEE ALSO"
+.IR bc (1),
+.SH BUGS
+With the input base set to 16, terms such as
+.B ABC
+are ambiguous.
+They are interpreted as numbers only if there is no function or variable of the same name.
+To force interpretation as a number, use the \fL0x\fR prefix.
+.PP
+Arbitrary bases should be supported, but are not supported by the 9front's
+.IR mp (2)
+string functions.
+.SH HISTORY
+.I Pc
+first appeared in 9front (August, 2016).
--- /dev/null
+++ b/pc.y
@@ -1,0 +1,1070 @@
+%{+#include <u.h>
+#include <libc.h>
+#include <bio.h>
+#include <ctype.h>
+#include <mp.h>
+#include <thread.h>
+#undef long
+#include <unistd.h>
+
+int inbase = 10, outbase, divmode, sep, heads, fail, prompt, eof;
+enum { MAXARGS = 16 };+
+typedef struct Num Num;
+struct Num {+ mpint;
+ int b;
+ Ref;
+};
+enum { STRONG = 0x100 };+
+void *
+emalloc(int n)
+{+ void *v;
+
+ v = malloc(n);
+ if(v == nil)
+ sysfatal("malloc: %r");+ memset(v, 0, n);
+ setmalloctag(v, getcallerpc(&n));
+ return v;
+}
+
+void *
+error(char *fmt, ...)
+{+ va_list va;
+ Fmt f;
+ char buf[256];
+
+ fmtfdinit(&f, 2, buf, sizeof(buf));
+ va_start(va, fmt);
+ fmtvprint(&f, fmt, va);
+ fmtrune(&f, '\n');
+ fmtfdflush(&f);
+ va_end(va);
+ fail++;
+ return nil;
+}
+
+Num *
+numalloc(void)
+{+ Num *r;
+
+ r = emalloc(sizeof(Num));
+ r->ref = 1;
+ r->p = emalloc(sizeof(mpdigit));
+ mpassign(mpzero, r);
+ return r;
+}
+
+Num *
+numincref(Num *n)
+{+ incref(n);
+ return n;
+}
+
+Num *
+numdecref(Num *n)
+{+ if(n == nil) return nil;
+ if(decref(n) == 0){+ free(n->p);
+ free(n);
+ return nil;
+ }
+ return n;
+}
+
+Num *
+nummod(Num *n)
+{+ Num *m;
+
+ if(n == nil) return nil;
+ if(n->ref == 1) return n;
+ m = numalloc();
+ mpassign(n, m);
+ m->b = n->b;
+ numdecref(n);
+ return m;
+}
+
+int
+basemax(int a, int b)
+{+ if(a == STRONG+10 && b >= STRONG) return b;
+ if(b == STRONG+10 && a >= STRONG) return a;
+ if(a == 10) return b;
+ if(b == 10) return a;
+ if(a < b) return b;
+ return a;
+}
+
+typedef struct Symbol Symbol;
+struct Symbol {+ enum {+ SYMNONE,
+ SYMVAR,
+ SYMFUNC,
+ } t;
+ Num *val;
+ int nargs;
+ Num *(*func)(int unused, Num **);
+ char *name;
+ Symbol *next;
+};
+Symbol *symtab[64];
+
+Symbol *
+getsym(char *n, int mk)
+{+ Symbol **p;
+ for(p = &symtab[*n&63]; *p != nil; p = &(*p)->next)
+ if(strcmp((*p)->name, n) == 0)
+ return *p;
+ if(!mk) return nil;
+ *p = emalloc(sizeof(Symbol));
+ (*p)->name = strdup(n);
+ return *p;
+}
+
+static void
+printhead(int n, int s, int sp, char *t)
+{+ char *q;
+ int i, j, k;
+
+ for(i = 1; i < n; i *= 10)
+ ;
+ while(i /= 10, i != 0){+ q = t;
+ *--q = 0;
+ for(j = 0, k = 0; j < n; j += s, k++){+ if(k == sep && sep != 0){+ *--q = ' ';
+ k = 0;
+ }
+ if(j >= i || j == 0 && i == 1)
+ *--q = '0' + j / i % 10;
+ else
+ *--q = ' ';
+ }
+ for(j = 0; j < sp; j++)
+ *--q = ' ';
+ print("%s\n", q);+ }
+}
+
+void
+numprint(Num *n)
+{+ int b;
+ int l, i, st, sp;
+ char *s, *t, *p, *q;
+
+ if(n == nil) return;
+ if(n->b >= STRONG || n->b != 0 && outbase == 0)
+ b = n->b & ~STRONG;
+ else if(outbase == 0)
+ b = 10;
+ else
+ b = outbase;
+ s = mptoa(n, b, nil, 0);
+ l = strlen(s);
+ t = emalloc(l * 2 + 4);
+ q = t + l * 2 + 4;
+ if(heads){+ switch(b){+ case 16: st = 4; sp = 2; break;
+ case 8: st = 3; sp = 1; break;
+ case 2: st = 1; sp = 2; break;
+ default: st = 0; sp = 0;
+ }
+ if(n->sign < 0)
+ sp++;
+ if(st != 0)
+ printhead(mpsignif(n), st, sp, q);
+ }
+ *--q = 0;
+ for(p = s + l - 1, i = 0; p >= s && *p != '-'; p--, i++){+ if(sep != 0 && i == sep){+ *--q = '_';
+ i = 0;
+ }
+ if(*p >= 'A')
+ *--q = *p + ('a' - 'A');+ else
+ *--q = *p;
+ }
+ if(mpcmp(n, mpzero) != 0)
+ switch(b){+ case 16: *--q = 'x'; *--q = '0'; break;
+ case 10: if(outbase != 0 && outbase != 10 || inbase != 10) {*--q = 'd'; *--q = '0';} break;+ case 8: *--q = '0'; break;
+ case 2: *--q = 'b'; *--q = '0'; break;
+ }
+ if(p >= s)
+ *--q = '-';
+ print("%s\n", q);+ free(s);
+ free(t);
+}
+
+void
+numdecrefs(int n, Num **x)
+{+ int i;
+
+ for(i = 0; i < n; i++)
+ numdecref(x[i]);
+}
+
+Num *
+fncall(Symbol *s, int n, Num **x)
+{+ int i;
+
+ if(s->t != SYMFUNC){+ numdecrefs(n, x);
+ return error("%s: not a function", s->name);+ }
+ else if(s->nargs >= 0 && s->nargs != n){+ numdecrefs(n, x);
+ return error("%s: wrong number of arguments", s->name);+ }
+ for(i = 0; i < n; i++)
+ if(x[i] == nil)
+ return nil;
+ return s->func(n, x);
+}
+
+Num *
+hexfix(Symbol *s)
+{+ char *b, *p, *q;
+
+ if(inbase != 16) return nil;
+ if(s->val != nil) return numincref(s->val);
+ if(strspn(s->name, "0123456789ABCDEFabcdef_") != strlen(s->name)) return nil;
+ b = strdup(s->name);
+ for(p = b, q = b; *p != 0; p++)
+ if(*p != '_')
+ *q++ = *p;
+ *q = 0;
+ s->val = numalloc();
+ strtomp(b, nil, 16, s->val);
+ s->val->b = 16;
+ free(b);
+ return numincref(s->val);
+}
+
+%}
+
+%token LOEXP LOLSH LORSH LOEQ LONE LOLE LOGE LOLAND LOLOR
+
+%union {+ Num *n;
+ Symbol *sym;
+ struct {+ Num *x[MAXARGS];
+ int n;
+ } args;
+}
+
+%token <n> LNUM
+%token <sym> LSYMB
+
+%type <n> expr
+%type <args> elist elist1
+
+%right '='
+%right '?'
+%left LOLOR
+%left LOLAND
+%left '|'
+%left '^'
+%left '&'
+%left LOEQ LONE
+%left '<' '>' LOLE LOGE
+%left LOLSH LORSH
+%left '+' '-'
+%left unary
+%left '*' '/' '%'
+%right LOEXP
+%right '$'
+
+%{+ int save;
+ Num *last;
+ Num *lastp;
+
+ extern Num *numbin(int op, Num *a, Num *b);
+ extern void yyerror(char *msg);
+ extern int yylex(void);
+%}
+
+%%
+
+input: | input line '\n' {+ if(!fail && last != nil) {+ numprint(last);
+ numdecref(lastp);
+ lastp = last;
+ }
+ fail = 0;
+ last = nil;
+ }
+
+line: stat
+ | line ';' stat
+
+stat: { last = nil; }+ | expr { last = $1; }+ | '_' { save = inbase; inbase = 10; } expr {+ inbase = save;
+ if(mpcmp($3, mpzero) < 0)
+ error("no.");+ if(!fail)
+ sep = mptoi($3);
+ numdecref($3);
+ numdecref(last);
+ last = nil;
+ }
+ | '<' { save = inbase; inbase = 10; } expr {+ inbase = save;
+ if(!fail)
+ inbase = mptoi($3);
+ if(inbase != 2 && inbase != 8 && inbase != 10 && inbase != 16){+ error("no.");+ inbase = save;
+ }
+ numdecref($3);
+ numdecref(last);
+ last = nil;
+ }
+ | '>' { save = inbase; inbase = 10; } expr {+ inbase = save;
+ save = outbase;
+ if(!fail)
+ outbase = mptoi($3);
+ if(outbase != 0 && outbase != 2 && outbase != 8 && outbase != 10 && outbase != 16){+ error("no.");+ outbase = save;
+ }
+ numdecref($3);
+ numdecref(last);
+ last = nil;
+ }
+ | '/' { save = inbase; inbase = 10; } expr {+ inbase = save;
+ save = divmode;
+ if(!fail)
+ divmode = mptoi($3);
+ if(divmode != 0 && divmode != 1){+ error("no.");+ divmode = save;
+ }
+ numdecref($3);
+ numdecref(last);
+ last = nil;
+ }
+ | '\'' { save = inbase; inbase = 10; } expr {+ inbase = save;
+ save = heads;
+ if(!fail)
+ heads = mptoi($3);
+ if(heads != 0 && heads != 1){+ error("no.");+ heads = save;
+ }
+ numdecref($3);
+ numdecref(last);
+ last = nil;
+ }
+ | error
+
+expr: LNUM
+ | '(' expr ')' { $$ = $2; }+ | expr '+' expr { $$ = numbin('+', $1, $3); }+ | expr '-' expr { $$ = numbin('-', $1, $3); }+ | expr '*' expr { $$ = numbin('*', $1, $3); }+ | expr '/' expr { $$ = numbin('/', $1, $3); }+ | expr '%' expr { $$ = numbin('%', $1, $3); }+ | expr '&' expr { $$ = numbin('&', $1, $3); }+ | expr '|' expr { $$ = numbin('|', $1, $3); }+ | expr '^' expr { $$ = numbin('^', $1, $3); } + | expr LOEXP expr { $$ = numbin(LOEXP, $1, $3); }+ | expr LOLSH expr { $$ = numbin(LOLSH, $1, $3); }+ | expr LORSH expr { $$ = numbin(LORSH, $1, $3); }+ | expr LOEQ expr { $$ = numbin(LOEQ, $1, $3); }+ | expr LONE expr { $$ = numbin(LONE, $1, $3); }+ | expr '<' expr { $$ = numbin('<', $1, $3); }+ | expr '>' expr { $$ = numbin('>', $1, $3); }+ | expr LOLE expr { $$ = numbin(LOLE, $1, $3); }+ | expr LOGE expr { $$ = numbin(LOGE, $1, $3); }+ | expr LOLAND expr { $$ = numbin(LOLAND, $1, $3); }+ | expr LOLOR expr { $$ = numbin(LOLOR, $1, $3); }+ | '+' expr %prec unary { $$ = $2; }+ | '-' expr %prec unary { $$ = nummod($2); if($$ != nil) mpsub(mpzero, $$, $$); }+ | '~' expr %prec unary { $$ = nummod($2); if($$ != nil) mpnot($$, $$); }+ | '!' expr %prec unary { $$ = nummod($2); if($$ != nil) {itomp(mpcmp($$, mpzero) == 0, $$); $$->b = 0; } }+ | '$' expr { $$ = nummod($2); if($$ != nil) {if($2->sign > 0) mpxtend($2, mpsignif($2), $$); else mpassign($2, $$); } }+ | expr '?' expr ':' expr %prec '?' {+ if($1 == nil || mpcmp($1, mpzero) != 0){+ $$ = $3;
+ numdecref($5);
+ }else{+ $$ = $5;
+ numdecref($3);
+ }
+ numdecref($1);
+ }
+ | LSYMB '(' elist ')' { $$ = fncall($1, $3.n, $3.x); }+ | LSYMB {+ Num *n;
+ $$ = nil;
+ switch($1->t){+ case SYMVAR: $$ = numincref($1->val); break;
+ case SYMNONE:
+ n = hexfix($1);
+ if(n != nil) $$ = n;
+ else error("%s undefined", $1->name);+ break;
+ case SYMFUNC: error("%s is a function", $1->name); break;+ default: error("%s invalid here", $1->name);+ }
+ }
+ | LSYMB '=' expr {+ if($1->t != SYMNONE && $1->t != SYMVAR)
+ error("%s redefined", $1->name);+ else if(!fail){+ $1->t = SYMVAR;
+ numdecref($1->val);
+ $1->val = numincref($3);
+ }
+ $$ = $3;
+ }
+ | '@' {+ $$ = lastp;
+ if($$ == nil) error("no last result");+ else numincref($$);
+ }
+ | expr '$' expr { $$ = numbin('$', $1, $3); }+
+elist: { $$.n = 0; } | elist1+elist1: expr { $$.x[0] = $1; $$.n = 1; }+ | elist1 ',' expr {+ $$ = $1;
+ if($$.n >= MAXARGS)
+ error("too many arguments");+ else
+ $$.x[$$.n++] = $3;
+ }
+
+%%
+
+typedef struct Keyword Keyword;
+struct Keyword {+ char *name;
+ int tok;
+};
+
+Keyword ops[] = {+ "**", LOEXP,
+ "<<", LOLSH,
+ "<=", LOLE,
+ ">>", LORSH,
+ ">=", LOGE,
+ "==", LOEQ,
+ "&&", LOLAND,
+ "||", LOLOR,
+ "", 0,
+};
+
+Keyword *optab[128];
+
+
+Biobuf *in;
+int prompted;
+
+Num *
+numbin(int op, Num *a, Num *b)
+{+ mpint *r;
+
+ if(fail || a == nil || b == nil) return nil;
+ a = nummod(a);
+ a->b = basemax(a->b, b->b);
+ switch(op){+ case '+': mpadd(a, b, a); break;
+ case '-': mpsub(a, b, a); break;
+ case '*': mpmul(a, b, a); break;
+ case '/':
+ if(mpcmp(b, mpzero) == 0){+ numdecref(a);
+ numdecref(b);
+ return error("division by zero");+ }
+ r = mpnew(0);
+ mpdiv(a, b, a, r);
+ if(!divmode && r->sign < 0){+ if(b->sign > 0)
+ mpsub(a, mpone, a);
+ else
+ mpadd(a, mpone, a);
+ }
+ mpfree(r);
+ break;
+ case '%':
+ if(mpcmp(b, mpzero) == 0){+ numdecref(a);
+ numdecref(b);
+ return error("division by zero");+ }
+ mpdiv(a, b, nil, a);
+ if(!divmode && a->sign < 0){+ if(b->sign > 0)
+ mpadd(a, b, a);
+ else
+ mpsub(a, b, a);
+ }
+ break;
+ case '&': mpand(a, b, a); break;
+ case '|': mpor(a, b, a); break;
+ case '^': mpxor(a, b, a); break;
+ case LOEXP:
+ if(mpcmp(b, mpzero) < 0){+ numdecref(a);
+ numdecref(b);
+ return error("negative exponent");+ }
+ mpexp(a, b, nil, a);
+ break;
+ case LOLSH:
+ if(mpsignif(b) >= 31){+ if(b->sign > 0)
+ error("left shift overflow");+ itomp(-(mpcmp(a, mpzero) < 0), a);
+ }else
+ mpasr(a, -mptoi(b), a);
+ break;
+ case LORSH:
+ if(mpsignif(b) >= 31){+ if(b->sign < 0)
+ error("right shift overflow");+ itomp(-(mpcmp(a, mpzero) < 0), a);
+ }else
+ mpasr(a, mptoi(b), a);
+ break;
+ case '<': itomp(mpcmp(a, b) < 0, a); a->b = 0; break;
+ case '>': itomp(mpcmp(a, b) > 0, a); a->b = 0; break;
+ case LOLE: itomp(mpcmp(a, b) <= 0, a); a->b = 0; break;
+ case LOGE: itomp(mpcmp(a, b) >= 0, a); a->b = 0; break;
+ case LOEQ: itomp(mpcmp(a, b) == 0, a); a->b = 0; break;
+ case LONE: itomp(mpcmp(a, b) != 0, a); a->b = 0; break;
+ case LOLAND:
+ a->b = b->b;
+ if(mpcmp(a, mpzero) == 0)
+ mpassign(mpzero, a);
+ else
+ mpassign(b, a);
+ break;
+ case LOLOR:
+ a->b = b->b;
+ if(mpcmp(a, mpzero) != 0)
+ mpassign(mpone, a);
+ else
+ mpassign(b, a);
+ break;
+ case '$':
+ a->b = b->b;
+ mpxtend(b, mptoi(a), a);
+ break;
+ }
+ numdecref(b);
+ return a;
+}
+int
+yylex(void)
+{+ int c, b;
+ char buf[512], *p;
+ Keyword *kw;
+
+ if(prompt && !prompted && !eof) {print("; "); prompted = 1;}+ do
+ c = Bgetc(in);
+ while(c != '\n' && isspace(c));
+ if(c < 0 && !eof){+ eof = 1;
+ c = '\n';
+ }
+ if(c == '\n')
+ prompted = 0;
+ if(isdigit(c)){+ for(p = buf, *p++ = c; c = Bgetc(in), isalnum(c) || c == '_'; )
+ if(p < buf + sizeof(buf) - 1 && c != '_')
+ *p++ = c;
+ *p = 0;
+ if(c >= 0) Bungetc(in);
+ b = inbase;
+ p = buf;
+ if(*p == '0'){+ p++;
+ switch(*p++){+ case 0: p -= 2; break;
+ case 'b': case 'B': b = 2; break;
+ case 'd': case 'D': b = 10; break;
+ case 'x': case 'X': b = 16; break;
+ default: p--; b = 8; break;
+ }
+ }
+ yylval.n = numalloc();
+ strtomp(p, &p, b, yylval.n);
+ if(*p != 0) error("not a number: %s", buf);+ yylval.n->b = b;
+ return LNUM;
+ }
+ if(isalpha(c) || c >= 0x80 || c == '_'){+ for(p = buf, *p++ = c; c = Bgetc(in), isalnum(c) || c >= 0x80 || c == '_'; )
+ if(p < buf + sizeof(buf) - 1)
+ *p++ = c;
+ *p = 0;
+ Bungetc(in);
+ if(buf[0] == '_' && buf[1] == 0) return '_';
+ yylval.sym = getsym(buf, 1);
+ return LSYMB;
+ }
+ if(c < 128 && (kw = optab[c], kw != nil)){+ b = Bgetc(in);
+ for(; kw->name[0] == c; kw++)
+ if(kw->name[0] == b)
+ return kw->tok;
+ if(c >= 0) Bungetc(in);
+ }
+ return c;
+}
+
+void
+yyerror(char *msg)
+{+ error("%s", msg);+}
+
+void
+regfunc(char *n, Num *(*f)(int unused, Num **), int nargs)
+{+ Symbol *s;
+
+ s = getsym(n, 1);
+ s->t = SYMFUNC;
+ s->func = f;
+ s->nargs = nargs;
+}
+
+int
+toint(Num *n, int *p, int mustpos)
+{+ if(mpsignif(n) > 31 || mustpos && mpcmp(n, mpzero) < 0){+ error("invalid argument");+ return -1;
+ }
+ if(p != nil)
+ *p = mptoi(n);
+ return 0;
+}
+
+Num *
+fnhex(int unused, Num **a)
+{+ Num *r;
+
+ r = nummod(a[0]);
+ r->b = STRONG | 16;
+ return r;
+}
+
+Num *
+fndec(int unused, Num **a)
+{+ Num *r;
+
+ r = nummod(a[0]);
+ r->b = STRONG | 10;
+ return r;
+}
+
+Num *
+fnoct(int unused, Num **a)
+{+ Num *r;
+
+ r = nummod(a[0]);
+ r->b = STRONG | 8;
+ return r;
+}
+
+Num *
+fnbin(int unused, Num **a)
+{+ Num *r;
+
+ r = nummod(a[0]);
+ r->b = STRONG | 2;
+ return r;
+}
+
+Num *
+fnpb(int unused, Num **a)
+{+ Num *r;
+ int b;
+
+ if(toint(a[1], &b, 1)){+ out:
+ numdecref(a[0]);
+ numdecref(a[1]);
+ return nil;
+ }
+ if(b != 0 && b != 2 && b != 8 && b != 10 && b != 16){+ error("unsupported base");+ goto out;
+ }
+ r = nummod(a[0]);
+ if(b == 0)
+ r->b = 0;
+ else
+ r->b = STRONG | b;
+ return r;
+}
+
+Num *
+fnabs(int unused, Num **a)
+{+ Num *r;
+
+ r = nummod(a[0]);
+ r->sign = 1;
+ return r;
+}
+
+Num *
+fnround(int unused, Num **a)
+{+ mpint *q, *r;
+ int i;
+
+ if(mpcmp(a[1], mpzero) <= 0){+ numdecref(a[0]);
+ numdecref(a[1]);
+ return error("invalid argument");+ }
+ q = mpnew(0);
+ r = mpnew(0);
+ a[0] = nummod(a[0]);
+ mpdiv(a[0], a[1], q, r);
+ if(r->sign < 0) mpadd(r, a[1], r);
+ mpleft(r, 1, r);
+ i = mpcmp(r, a[1]);
+ mpright(r, 1, r);
+ if(i > 0 || i == 0 && (a[0]->sign < 0) ^ (q->top != 0 && (q->p[0] & 1) != 0))
+ mpsub(r, a[1], r);
+ mpsub(a[0], r, a[0]);
+ mpfree(q);
+ mpfree(r);
+ numdecref(a[1]);
+ return a[0];
+}
+
+Num *
+fnfloor(int unused, Num **a)
+{+ mpint *r;
+
+ if(mpcmp(a[1], mpzero) <= 0){+ numdecref(a[0]);
+ numdecref(a[1]);
+ return error("invalid argument");+ }
+ r = mpnew(0);
+ a[0] = nummod(a[0]);
+ mpdiv(a[0], a[1], nil, r);
+ if(r->sign < 0) mpadd(r, a[1], r);
+ mpsub(a[0], r, a[0]);
+ mpfree(r);
+ numdecref(a[1]);
+ return a[0];
+}
+
+Num *
+fnceil(int unused, Num **a)
+{+ mpint *r;
+
+ if(mpcmp(a[1], mpzero) <= 0){+ numdecref(a[0]);
+ numdecref(a[1]);
+ return error("invalid argument");+ }
+ r = mpnew(0);
+ a[0] = nummod(a[0]);
+ mpdiv(a[0], a[1], nil, r);
+ if(r->sign < 0) mpadd(r, a[1], r);
+ if(mpcmp(r, mpzero) != 0){+ mpsub(a[0], r, a[0]);
+ mpadd(a[0], a[1], a[0]);
+ }
+ mpfree(r);
+ numdecref(a[1]);
+ return a[0];
+}
+
+Num *
+fntrunc(int unused, Num **a)
+{+ int i;
+
+ if(toint(a[1], &i, 1)){+ numdecref(a[0]);
+ numdecref(a[1]);
+ return nil;
+ }
+ a[0] = nummod(a[0]);
+ mptrunc(a[0], i, a[0]);
+ return a[0];
+}
+
+Num *
+fnxtend(int unused, Num **a)
+{+ int i;
+
+ if(toint(a[1], &i, 1)) return nil;
+ a[0] = nummod(a[0]);
+ mpxtend(a[0], i, a[0]);
+ return a[0];
+}
+
+Num *
+fnclog(int n, Num **a)
+{+ int r;
+
+ if(n != 1 && n != 2){+ numdecrefs(n, a);
+ return error("clog: wrong number of arguments");+ }
+ if(mpcmp(a[0], mpzero) <= 0 || n == 2 && mpcmp(a[1], mpone) <= 0){+ numdecref(a[0]);
+ return error("invalid argument");+ }
+ if(n == 1 || mpcmp(a[1], mptwo) == 0){+ a[0] = nummod(a[0]);
+ mpsub(a[0], mpone, a[0]);
+ itomp(mpsignif(a[0]), a[0]);
+ a[0]->b = 0;
+ if(n == 2) numdecref(a[1]);
+ return a[0];
+ }
+ a[0] = nummod(a[0]);
+ for(r = 0; mpcmp(a[0], mpone) > 0; r++){+ mpadd(a[0], a[1], a[0]);
+ mpsub(a[0], mpone, a[0]);
+ mpdiv(a[0], a[1], a[0], nil);
+ }
+ itomp(r, a[0]);
+ a[0]->b = 0;
+ numdecref(a[1]);
+ return a[0];
+}
+
+Num *
+fnubits(int unused, Num **a)
+{+ if(a[0]->sign < 0){+ numdecref(a[0]);
+ return error("invalid argument");+ }
+ a[0] = nummod(a[0]);
+ itomp(mpsignif(a[0]), a[0]);
+ a[0]->b = 0;
+ return a[0];
+}
+
+Num *
+fnsbits(int unused, Num **a)
+{+ a[0] = nummod(a[0]);
+ if(a[0]->sign < 0) mpadd(a[0], mpone, a[0]);
+ itomp(mpsignif(a[0]) + 1, a[0]);
+ a[0]->b = 0;
+ return a[0];
+}
+
+Num *
+fnnsa(int unused, Num **a)
+{+ int n, i;
+ mpdigit d;
+
+ a[0] = nummod(a[0]);
+ if(a[0]->sign < 0){+ numdecref(a[0]);
+ return error("invalid argument");+ }
+ n = 0;
+ for(i = 0; i < a[0]->top; i++){+ d = a[0]->p[i];
+ for(; d != 0; d &= d-1)
+ n++;
+ }
+ itomp(n, a[0]);
+ a[0]->b = 0;
+ return a[0];
+}
+
+Num *
+fngcd(int unused, Num **a)
+{+ a[0] = nummod(a[0]);
+ a[0]->b = basemax(a[0]->b, a[1]->b);
+ mpextendedgcd(a[0], a[1], a[0], nil, nil);
+ return a[0];
+}
+
+Num *
+fnrand(int unused, Num **a)
+{+ Num *n;
+
+ n = numalloc();
+ n->b = a[0]->b;
+ mpnrand(a[0], genrandom, n);
+ numdecref(a[0]);
+ return n;
+}
+
+Num *
+fnminv(int unused, Num **a)
+{+ mpint *x;
+
+ a[0] = nummod(a[0]);
+ x = mpnew(0);
+ mpextendedgcd(a[0], a[1], x, a[0], nil);
+ if(mpcmp(x, mpone) != 0)
+ error("no modular inverse");+ else
+ mpmod(a[0], a[1], a[0]);
+ mpfree(x);
+ numdecref(a[1]);
+ return a[0];
+}
+
+Num *
+fnrev(int unused, Num **a)
+{+ mpdigit v, m;
+ int i, j, n;
+
+ if(toint(a[1], &n, 1)){+ numdecref(a[0]);
+ numdecref(a[1]);
+ return nil;
+ }
+ a[0] = nummod(a[0]);
+ mptrunc(a[0], n, a[0]);
+ for(i = 0; i < a[0]->top; i++){+ v = a[0]->p[i];
+ m = -1;
+ for(j = sizeof(mpdigit) * 8; j >>= 1; ){+ m ^= m << j;
+ v = v >> j & m | v << j & ~m;
+ }
+ a[0]->p[i] = v;
+ }
+ for(i = 0; i < a[0]->top / 2; i++){+ v = a[0]->p[i];
+ a[0]->p[i] = a[0]->p[a[0]->top - 1 - i];
+ a[0]->p[a[0]->top - 1 - i] = v;
+ }
+ mpleft(a[0], n - a[0]->top * sizeof(mpdigit) * 8, a[0]);
+ numdecref(a[1]);
+ return a[0];
+}
+
+Num *
+fncat(int n, Num **a)
+{+ int i, w;
+ Num *r;
+
+ if(n % 2 != 0){+ error("cat: odd number of arguments");+ i = 0;
+ fail:
+ for(; i < n; i++)
+ numdecref(a[i]);
+ return nil;
+ }
+ r = numalloc();
+ for(i = 0; i < n; i += 2){+ if(toint(a[i+1], &w, 1)) goto fail;
+ mpleft(r, w, r);
+ if(a[i]->sign < 0 || mpsignif(a[i]) > w){+ a[i] = nummod(a[i]);
+ mptrunc(a[i], w, a[i]);
+ }
+ r->b = basemax(r->b, a[i]->b);
+ mpor(r, a[i], r);
+ numdecref(a[i]);
+ numdecref(a[i+1]);
+ }
+ return r;
+}
+
+int
+main(int argc, char **argv)
+{+ Keyword *kw;
+
+ fmtinstall('B', mpfmt);+
+ for(kw = ops; kw->name[0] != 0; kw++)
+ if(optab[kw->name[0]] == nil)
+ optab[kw->name[0]] = kw;
+
+ regfunc("hex", fnhex, 1);+ regfunc("dec", fndec, 1);+ regfunc("oct", fnoct, 1);+ regfunc("bin", fnbin, 1);+ regfunc("pb", fnpb, 2);+ regfunc("abs", fnabs, 1);+ regfunc("round", fnround, 2);+ regfunc("floor", fnfloor, 2);+ regfunc("ceil", fnceil, 2);+ regfunc("trunc", fntrunc, 2);+ regfunc("xtend", fnxtend, 2);+ regfunc("clog", fnclog, -1);+ regfunc("ubits", fnubits, 1);+ regfunc("sbits", fnsbits, 1);+ regfunc("nsa", fnnsa, 1);+ regfunc("gcd", fngcd, 2);+ regfunc("minv", fnminv, 2);+ regfunc("rand", fnrand, 1);+ regfunc("rev", fnrev, 2);+ regfunc("cat", fncat, -1);+
+ prompt = isatty(fileno(stdin));
+
+ in = Bfdopen(0, OREAD);
+ if(in == nil) sysfatal("Bfdopen: %r");+ yyparse();
+ extern int yynerrs;
+ return yynerrs ? 1 : 0;
+}