diff options
author | Taru Karttunen <taruti@taruti.net> | 2011-03-30 15:46:40 +0300 |
---|---|---|
committer | Taru Karttunen <taruti@taruti.net> | 2011-03-30 15:46:40 +0300 |
commit | e5888a1ffdae813d7575f5fb02275c6bb07e5199 (patch) | |
tree | d8d51eac403f07814b9e936eed0c9a79195e2450 /sys/src/libc/port |
Import sources from 2011-03-30 iso image
Diffstat (limited to 'sys/src/libc/port')
112 files changed, 8919 insertions, 0 deletions
diff --git a/sys/src/libc/port/_assert.c b/sys/src/libc/port/_assert.c new file mode 100755 index 000000000..929e4c113 --- /dev/null +++ b/sys/src/libc/port/_assert.c @@ -0,0 +1,13 @@ +#include <u.h> +#include <libc.h> + +void (*__assert)(char*); + +void +_assert(char *s) +{ + if(__assert) + (*__assert)(s); + fprint(2, "assert failed: %s\n", s); + abort(); +} diff --git a/sys/src/libc/port/abs.c b/sys/src/libc/port/abs.c new file mode 100755 index 000000000..7e8adda55 --- /dev/null +++ b/sys/src/libc/port/abs.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> + +int +abs(int a) +{ + if(a < 0) + return -a; + return a; +} + +long +labs(long a) +{ + if(a < 0) + return -a; + return a; +} diff --git a/sys/src/libc/port/asin.c b/sys/src/libc/port/asin.c new file mode 100755 index 000000000..7cb1455ed --- /dev/null +++ b/sys/src/libc/port/asin.c @@ -0,0 +1,40 @@ +/* + * asin(arg) and acos(arg) return the arcsin, arccos, + * respectively of their arguments. + * + * Arctan is called after appropriate range reduction. + */ + +#include <u.h> +#include <libc.h> + +double +asin(double arg) +{ + double temp; + int sign; + + sign = 0; + if(arg < 0) { + arg = -arg; + sign++; + } + if(arg > 1) + return NaN(); + temp = sqrt(1 - arg*arg); + if(arg > 0.7) + temp = PIO2 - atan(temp/arg); + else + temp = atan(arg/temp); + if(sign) + temp = -temp; + return temp; +} + +double +acos(double arg) +{ + if(arg > 1 || arg < -1) + return NaN(); + return PIO2 - asin(arg); +} diff --git a/sys/src/libc/port/atan.c b/sys/src/libc/port/atan.c new file mode 100755 index 000000000..4de3a2218 --- /dev/null +++ b/sys/src/libc/port/atan.c @@ -0,0 +1,78 @@ +/* + floating-point arctangent + + atan returns the value of the arctangent of its + argument in the range [-pi/2,pi/2]. + + atan2 returns the arctangent of arg1/arg2 + in the range [-pi,pi]. + + there are no error returns. + + coefficients are #5077 from Hart & Cheney. (19.56D) +*/ + +#include <u.h> +#include <libc.h> + +#define sq2p1 2.414213562373095048802e0 +#define sq2m1 .414213562373095048802e0 +#define p4 .161536412982230228262e2 +#define p3 .26842548195503973794141e3 +#define p2 .11530293515404850115428136e4 +#define p1 .178040631643319697105464587e4 +#define p0 .89678597403663861959987488e3 +#define q4 .5895697050844462222791e2 +#define q3 .536265374031215315104235e3 +#define q2 .16667838148816337184521798e4 +#define q1 .207933497444540981287275926e4 +#define q0 .89678597403663861962481162e3 + + +/* + xatan evaluates a series valid in the + range [-0.414...,+0.414...]. (tan(pi/8)) + */ + +static +double +xatan(double arg) +{ + double argsq, value; + + argsq = arg*arg; + value = ((((p4*argsq + p3)*argsq + p2)*argsq + p1)*argsq + p0); + value = value/(((((argsq + q4)*argsq + q3)*argsq + q2)*argsq + q1)*argsq + q0); + return value*arg; +} + +/* + satan reduces its argument (known to be positive) + to the range [0,0.414...] and calls xatan. + */ + +static +double +satan(double arg) +{ + + if(arg < sq2m1) + return xatan(arg); + if(arg > sq2p1) + return PIO2 - xatan(1/arg); + return PIO2/2 + xatan((arg-1)/(arg+1)); +} + +/* + atan makes its argument positive and + calls the inner routine satan. + */ + +double +atan(double arg) +{ + + if(arg > 0) + return satan(arg); + return -satan(-arg); +} diff --git a/sys/src/libc/port/atan2.c b/sys/src/libc/port/atan2.c new file mode 100755 index 000000000..480eb4c67 --- /dev/null +++ b/sys/src/libc/port/atan2.c @@ -0,0 +1,24 @@ +#include <u.h> +#include <libc.h> +/* + atan2 discovers what quadrant the angle + is in and calls atan. +*/ + +double +atan2(double arg1, double arg2) +{ + + if(arg1+arg2 == arg1) { + if(arg1 >= 0) + return PIO2; + return -PIO2; + } + arg1 = atan(arg1/arg2); + if(arg2 < 0) { + if(arg1 <= 0) + return arg1 + PI; + return arg1 - PI; + } + return arg1; +} diff --git a/sys/src/libc/port/atexit.c b/sys/src/libc/port/atexit.c new file mode 100755 index 000000000..e9cb6c297 --- /dev/null +++ b/sys/src/libc/port/atexit.c @@ -0,0 +1,60 @@ +#include <u.h> +#include <libc.h> + +#define NEXIT 33 + +typedef struct Onex Onex; +struct Onex{ + void (*f)(void); + int pid; +}; + +static Lock onexlock; +Onex onex[NEXIT]; + +int +atexit(void (*f)(void)) +{ + int i; + + lock(&onexlock); + for(i=0; i<NEXIT; i++) + if(onex[i].f == 0) { + onex[i].pid = getpid(); + onex[i].f = f; + unlock(&onexlock); + return 1; + } + unlock(&onexlock); + return 0; +} + +void +atexitdont(void (*f)(void)) +{ + int i, pid; + + pid = getpid(); + for(i=0; i<NEXIT; i++) + if(onex[i].f == f && onex[i].pid == pid) + onex[i].f = 0; +} + +#pragma profile off + +void +exits(char *s) +{ + int i, pid; + void (*f)(void); + + pid = getpid(); + for(i = NEXIT-1; i >= 0; i--) + if((f = onex[i].f) && pid == onex[i].pid) { + onex[i].f = 0; + (*f)(); + } + _exits(s); +} + +#pragma profile on diff --git a/sys/src/libc/port/atnotify.c b/sys/src/libc/port/atnotify.c new file mode 100755 index 000000000..60e8ad0c0 --- /dev/null +++ b/sys/src/libc/port/atnotify.c @@ -0,0 +1,58 @@ +#include <u.h> +#include <libc.h> + +#define NFN 33 +static int (*onnot[NFN])(void*, char*); +static Lock onnotlock; + +static +void +notifier(void *v, char *s) +{ + int i; + + for(i=0; i<NFN; i++) + if(onnot[i] && ((*onnot[i])(v, s))){ + noted(NCONT); + return; + } + noted(NDFLT); +} + +int +atnotify(int (*f)(void*, char*), int in) +{ + int i, n, ret; + static int init; + + if(!init){ + notify(notifier); + init = 1; /* assign = */ + } + ret = 0; + lock(&onnotlock); + if(in){ + for(i=0; i<NFN; i++) + if(onnot[i] == 0) { + onnot[i] = f; + ret = 1; + break; + } + }else{ + n = 0; + for(i=0; i<NFN; i++) + if(onnot[i]){ + if(ret==0 && onnot[i]==f){ + onnot[i] = 0; + ret = 1; + }else + n++; + } + if(n == 0){ + init = 0; + notify(0); + } + } + unlock(&onnotlock); + return ret; +} diff --git a/sys/src/libc/port/atof.c b/sys/src/libc/port/atof.c new file mode 100755 index 000000000..ed8cbeeb8 --- /dev/null +++ b/sys/src/libc/port/atof.c @@ -0,0 +1,8 @@ +#include <u.h> +#include <libc.h> + +double +atof(char *cp) +{ + return strtod(cp, 0); +} diff --git a/sys/src/libc/port/atol.c b/sys/src/libc/port/atol.c new file mode 100755 index 000000000..6928da7bd --- /dev/null +++ b/sys/src/libc/port/atol.c @@ -0,0 +1,53 @@ +#include <u.h> +#include <libc.h> + +long +atol(char *s) +{ + long n; + int f, c; + + n = 0; + f = 0; + while(*s == ' ' || *s == '\t') + s++; + if(*s == '-' || *s == '+') { + if(*s++ == '-') + f = 1; + while(*s == ' ' || *s == '\t') + s++; + } + if(s[0]=='0' && s[1]) { + if(s[1]=='x' || s[1]=='X'){ + s += 2; + for(;;) { + c = *s; + if(c >= '0' && c <= '9') + n = n*16 + c - '0'; + else + if(c >= 'a' && c <= 'f') + n = n*16 + c - 'a' + 10; + else + if(c >= 'A' && c <= 'F') + n = n*16 + c - 'A' + 10; + else + break; + s++; + } + } else + while(*s >= '0' && *s <= '7') + n = n*8 + *s++ - '0'; + } else + while(*s >= '0' && *s <= '9') + n = n*10 + *s++ - '0'; + if(f) + n = -n; + return n; +} + +int +atoi(char *s) +{ + + return atol(s); +} diff --git a/sys/src/libc/port/atoll.c b/sys/src/libc/port/atoll.c new file mode 100755 index 000000000..b4497de59 --- /dev/null +++ b/sys/src/libc/port/atoll.c @@ -0,0 +1,8 @@ +#include <u.h> +#include <libc.h> + +vlong +atoll(char *s) +{ + return strtoll(s, nil, 0); +} diff --git a/sys/src/libc/port/charstod.c b/sys/src/libc/port/charstod.c new file mode 100755 index 000000000..0df775481 --- /dev/null +++ b/sys/src/libc/port/charstod.c @@ -0,0 +1,81 @@ +#include <u.h> +#include <libc.h> + +/* + * Reads a floating-point number by interpreting successive characters + * returned by (*f)(vp). The last call it makes to f terminates the + * scan, so is not a character in the number. It may therefore be + * necessary to back up the input stream up one byte after calling charstod. + */ + +#define ADVANCE *s++ = c; if(s>=e) return NaN(); c = (*f)(vp) + +double +charstod(int(*f)(void*), void *vp) +{ + char str[400], *s, *e, *start; + int c; + + s = str; + e = str + sizeof str - 1; + c = (*f)(vp); + while(c == ' ' || c == '\t') + c = (*f)(vp); + if(c == '-' || c == '+'){ + ADVANCE; + } + start = s; + while(c >= '0' && c <= '9'){ + ADVANCE; + } + if(c == '.'){ + ADVANCE; + while(c >= '0' && c <= '9'){ + ADVANCE; + } + } + if(s > start && (c == 'e' || c == 'E')){ + ADVANCE; + if(c == '-' || c == '+'){ + ADVANCE; + } + while(c >= '0' && c <= '9'){ + ADVANCE; + } + }else if(s == start && (c == 'i' || c == 'I')){ + ADVANCE; + if(c != 'n' && c != 'N') + return NaN(); + ADVANCE; + if(c != 'f' && c != 'F') + return NaN(); + ADVANCE; + if(c != 'i' && c != 'I') + return NaN(); + ADVANCE; + if(c != 'n' && c != 'N') + return NaN(); + ADVANCE; + if(c != 'i' && c != 'I') + return NaN(); + ADVANCE; + if(c != 't' && c != 'T') + return NaN(); + ADVANCE; + if(c != 'y' && c != 'Y') + return NaN(); + ADVANCE; /* so caller can back up uniformly */ + USED(c); + }else if(s == str && (c == 'n' || c == 'N')){ + ADVANCE; + if(c != 'a' && c != 'A') + return NaN(); + ADVANCE; + if(c != 'n' && c != 'N') + return NaN(); + ADVANCE; /* so caller can back up uniformly */ + USED(c); + } + *s = 0; + return strtod(str, &s); +} diff --git a/sys/src/libc/port/cistrcmp.c b/sys/src/libc/port/cistrcmp.c new file mode 100755 index 000000000..a545615b7 --- /dev/null +++ b/sys/src/libc/port/cistrcmp.c @@ -0,0 +1,26 @@ +#include <u.h> +#include <libc.h> + +int +cistrcmp(char *s1, char *s2) +{ + int c1, c2; + + while(*s1){ + c1 = *(uchar*)s1++; + c2 = *(uchar*)s2++; + + if(c1 == c2) + continue; + + if(c1 >= 'A' && c1 <= 'Z') + c1 -= 'A' - 'a'; + + if(c2 >= 'A' && c2 <= 'Z') + c2 -= 'A' - 'a'; + + if(c1 != c2) + return c1 - c2; + } + return -*s2; +} diff --git a/sys/src/libc/port/cistrncmp.c b/sys/src/libc/port/cistrncmp.c new file mode 100755 index 000000000..8f24d411f --- /dev/null +++ b/sys/src/libc/port/cistrncmp.c @@ -0,0 +1,28 @@ +#include <u.h> +#include <libc.h> + +int +cistrncmp(char *s1, char *s2, int n) +{ + int c1, c2; + + while(*s1 && n-- > 0){ + c1 = *(uchar*)s1++; + c2 = *(uchar*)s2++; + + if(c1 == c2) + continue; + + if(c1 >= 'A' && c1 <= 'Z') + c1 -= 'A' - 'a'; + + if(c2 >= 'A' && c2 <= 'Z') + c2 -= 'A' - 'a'; + + if(c1 != c2) + return c1 - c2; + } + if(n <= 0) + return 0; + return -*s2; +} diff --git a/sys/src/libc/port/cistrstr.c b/sys/src/libc/port/cistrstr.c new file mode 100755 index 000000000..0a1132266 --- /dev/null +++ b/sys/src/libc/port/cistrstr.c @@ -0,0 +1,23 @@ +#include <u.h> +#include <libc.h> + +char* +cistrstr(char *s, char *sub) +{ + int c, csub, n; + + csub = *sub; + if(csub == '\0') + return s; + if(csub >= 'A' && csub <= 'Z') + csub -= 'A' - 'a'; + sub++; + n = strlen(sub); + for(; c = *s; s++){ + if(c >= 'A' && c <= 'Z') + c -= 'A' - 'a'; + if(c == csub && cistrncmp(s+1, sub, n) == 0) + return s; + } + return nil; +} diff --git a/sys/src/libc/port/cleanname.c b/sys/src/libc/port/cleanname.c new file mode 100755 index 000000000..1dae7bb84 --- /dev/null +++ b/sys/src/libc/port/cleanname.c @@ -0,0 +1,63 @@ +#include <u.h> +#include <libc.h> + +/* + * In place, rewrite name to compress multiple /, eliminate ., and process .. + */ +#define SEP(x) ((x)=='/' || (x) == 0) +char* +cleanname(char *name) +{ + char *p, *q, *dotdot; + int rooted, erasedprefix; + + rooted = name[0] == '/'; + erasedprefix = 0; + + /* + * invariants: + * p points at beginning of path element we're considering. + * q points just past the last path element we wrote (no slash). + * dotdot points just past the point where .. cannot backtrack + * any further (no slash). + */ + p = q = dotdot = name+rooted; + while(*p) { + if(p[0] == '/') /* null element */ + p++; + else if(p[0] == '.' && SEP(p[1])) { + if(p == name) + erasedprefix = 1; + p += 1; /* don't count the separator in case it is nul */ + } else if(p[0] == '.' && p[1] == '.' && SEP(p[2])) { + p += 2; + if(q > dotdot) { /* can backtrack */ + while(--q > dotdot && *q != '/') + ; + } else if(!rooted) { /* /.. is / but ./../ is .. */ + if(q != name) + *q++ = '/'; + *q++ = '.'; + *q++ = '.'; + dotdot = q; + } + if(q == name) + erasedprefix = 1; /* erased entire path via dotdot */ + } else { /* real path element */ + if(q != name+rooted) + *q++ = '/'; + while((*q = *p) != '/' && *q != 0) + p++, q++; + } + } + if(q == name) /* empty string is really ``.'' */ + *q++ = '.'; + *q = '\0'; + if(erasedprefix && name[0] == '#'){ + /* this was not a #x device path originally - make it not one now */ + memmove(name+2, name, strlen(name)+1); + name[0] = '.'; + name[1] = '/'; + } + return name; +} diff --git a/sys/src/libc/port/crypt.c b/sys/src/libc/port/crypt.c new file mode 100755 index 000000000..0524c9422 --- /dev/null +++ b/sys/src/libc/port/crypt.c @@ -0,0 +1,68 @@ +/* + * Data Encryption Standard + * D.P.Mitchell 83/06/08. + * + * block_cipher(key, block, decrypting) + * + * these routines use the non-standard 7 byte format + * for DES keys. + */ +#include <u.h> +#include <libc.h> +#include <auth.h> +#include <libsec.h> + +/* + * destructively encrypt the buffer, which + * must be at least 8 characters long. + */ +int +encrypt(void *key, void *vbuf, int n) +{ + ulong ekey[32]; + uchar *buf; + int i, r; + + if(n < 8) + return 0; + key_setup(key, ekey); + buf = vbuf; + n--; + r = n % 7; + n /= 7; + for(i = 0; i < n; i++){ + block_cipher(ekey, buf, 0); + buf += 7; + } + if(r) + block_cipher(ekey, buf - 7 + r, 0); + return 1; +} + +/* + * destructively decrypt the buffer, which + * must be at least 8 characters long. + */ +int +decrypt(void *key, void *vbuf, int n) +{ + ulong ekey[128]; + uchar *buf; + int i, r; + + if(n < 8) + return 0; + key_setup(key, ekey); + buf = vbuf; + n--; + r = n % 7; + n /= 7; + buf += n * 7; + if(r) + block_cipher(ekey, buf - 7 + r, 1); + for(i = 0; i < n; i++){ + buf -= 7; + block_cipher(ekey, buf, 1); + } + return 1; +} diff --git a/sys/src/libc/port/ctype.c b/sys/src/libc/port/ctype.c new file mode 100755 index 000000000..cfe1ed48a --- /dev/null +++ b/sys/src/libc/port/ctype.c @@ -0,0 +1,25 @@ +#include <u.h> +#include <libc.h> +#include <ctype.h> + +uchar _ctype[256] = +{ +/* 0 1 2 3 4 5 6 7 */ + +/* 0*/ _C, _C, _C, _C, _C, _C, _C, _C, +/* 10*/ _C, _S|_C, _S|_C, _S|_C, _S|_C, _S|_C, _C, _C, +/* 20*/ _C, _C, _C, _C, _C, _C, _C, _C, +/* 30*/ _C, _C, _C, _C, _C, _C, _C, _C, +/* 40*/ _S|_B, _P, _P, _P, _P, _P, _P, _P, +/* 50*/ _P, _P, _P, _P, _P, _P, _P, _P, +/* 60*/ _N|_X, _N|_X, _N|_X, _N|_X, _N|_X, _N|_X, _N|_X, _N|_X, +/* 70*/ _N|_X, _N|_X, _P, _P, _P, _P, _P, _P, +/*100*/ _P, _U|_X, _U|_X, _U|_X, _U|_X, _U|_X, _U|_X, _U, +/*110*/ _U, _U, _U, _U, _U, _U, _U, _U, +/*120*/ _U, _U, _U, _U, _U, _U, _U, _U, +/*130*/ _U, _U, _U, _P, _P, _P, _P, _P, +/*140*/ _P, _L|_X, _L|_X, _L|_X, _L|_X, _L|_X, _L|_X, _L, +/*150*/ _L, _L, _L, _L, _L, _L, _L, _L, +/*160*/ _L, _L, _L, _L, _L, _L, _L, _L, +/*170*/ _L, _L, _L, _P, _P, _P, _P, _C, +}; diff --git a/sys/src/libc/port/encodefmt.c b/sys/src/libc/port/encodefmt.c new file mode 100755 index 000000000..721a58c9f --- /dev/null +++ b/sys/src/libc/port/encodefmt.c @@ -0,0 +1,77 @@ +#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 = enc32(out, len, b, ilen); + break; + case '[': + rv = enc64(out, len, b, ilen); + break; + case 'H': + rv = enc16(out, len, b, ilen); + if(rv >= 0 && (f->flags & FmtLong)) + for(p = buf; *p; p++) + *p = tolower(*p); + break; + default: + rv = -1; + break; + } + if(rv < 0) + goto error; + + fmtstrcpy(f, buf); + if(buf != obuf) + free(buf); + return 0; + +error: + return fmtstrcpy(f, "<encodefmt>"); +} diff --git a/sys/src/libc/port/execl.c b/sys/src/libc/port/execl.c new file mode 100755 index 000000000..40574fe63 --- /dev/null +++ b/sys/src/libc/port/execl.c @@ -0,0 +1,9 @@ +#include <u.h> +#include <libc.h> + +int +execl(char *f, ...) +{ + + return exec(f, &f+1); +} diff --git a/sys/src/libc/port/exp.c b/sys/src/libc/port/exp.c new file mode 100755 index 000000000..0a3e9e444 --- /dev/null +++ b/sys/src/libc/port/exp.c @@ -0,0 +1,40 @@ +/* + exp returns the exponential function of its + floating-point argument. + + The coefficients are #1069 from Hart and Cheney. (22.35D) +*/ + +#include <u.h> +#include <libc.h> + +#define p0 .2080384346694663001443843411e7 +#define p1 .3028697169744036299076048876e5 +#define p2 .6061485330061080841615584556e2 +#define q0 .6002720360238832528230907598e7 +#define q1 .3277251518082914423057964422e6 +#define q2 .1749287689093076403844945335e4 +#define log2e 1.4426950408889634073599247 +#define sqrt2 1.4142135623730950488016887 +#define maxf 10000 + +double +exp(double arg) +{ + double fract, temp1, temp2, xsq; + int ent; + + if(arg == 0) + return 1; + if(arg < -maxf) + return 0; + if(arg > maxf) + return Inf(1); + arg *= log2e; + ent = floor(arg); + fract = (arg-ent) - 0.5; + xsq = fract*fract; + temp1 = ((p2*xsq+p1)*xsq+p0)*fract; + temp2 = ((xsq+q2)*xsq+q1)*xsq + q0; + return ldexp(sqrt2*(temp2+temp1)/(temp2-temp1), ent); +} diff --git a/sys/src/libc/port/fabs.c b/sys/src/libc/port/fabs.c new file mode 100755 index 000000000..9e90a6786 --- /dev/null +++ b/sys/src/libc/port/fabs.c @@ -0,0 +1,11 @@ +#include <u.h> +#include <libc.h> + +double +fabs(double arg) +{ + + if(arg < 0) + return -arg; + return arg; +} diff --git a/sys/src/libc/port/floor.c b/sys/src/libc/port/floor.c new file mode 100755 index 000000000..e1ee76489 --- /dev/null +++ b/sys/src/libc/port/floor.c @@ -0,0 +1,27 @@ +#include <u.h> +#include <libc.h> +/* + * floor and ceil-- greatest integer <= arg + * (resp least >=) + */ + +double +floor(double d) +{ + double fract; + + if(d < 0) { + fract = modf(-d, &d); + if(fract != 0.0) + d += 1; + d = -d; + } else + modf(d, &d); + return d; +} + +double +ceil(double d) +{ + return -floor(-d); +} diff --git a/sys/src/libc/port/fmod.c b/sys/src/libc/port/fmod.c new file mode 100755 index 000000000..3b97a5b43 --- /dev/null +++ b/sys/src/libc/port/fmod.c @@ -0,0 +1,31 @@ +#include <u.h> +#include <libc.h> + +/* + * floating-point mod function without infinity or NaN checking + */ +double +fmod (double x, double y) +{ + int sign, yexp, rexp; + double r, yfr, rfr; + + if (y == 0) + return x; + if (y < 0) + y = -y; + yfr = frexp(y, &yexp); + sign = 0; + if(x < 0) { + r = -x; + sign++; + } else + r = x; + while(r >= y) { + rfr = frexp(r, &rexp); + r -= ldexp(y, rexp - yexp - (rfr < yfr)); + } + if(sign) + r = -r; + return r; +} diff --git a/sys/src/libc/port/frand.c b/sys/src/libc/port/frand.c new file mode 100755 index 000000000..e13e1d860 --- /dev/null +++ b/sys/src/libc/port/frand.c @@ -0,0 +1,17 @@ +#include <u.h> +#include <libc.h> + +#define MASK 0x7fffffffL +#define NORM (1.0/(1.0+MASK)) + +double +frand(void) +{ + double x; + + do { + x = lrand() * NORM; + x = (x + lrand()) * NORM; + } while(x >= 1); + return x; +} diff --git a/sys/src/libc/port/frexp.c b/sys/src/libc/port/frexp.c new file mode 100755 index 000000000..7809bd151 --- /dev/null +++ b/sys/src/libc/port/frexp.c @@ -0,0 +1,105 @@ +#include <u.h> +#include <libc.h> + +/* + * this is big/little endian non-portable + * it gets the endian from the FPdbleword + * union in u.h. + */ +#define MASK 0x7ffL +#define SHIFT 20 +#define BIAS 1022L + +double +frexp(double d, int *ep) +{ + FPdbleword x; + + if(d == 0) { + *ep = 0; + return 0; + } + x.x = d; + *ep = ((x.hi >> SHIFT) & MASK) - BIAS; + x.hi &= ~(MASK << SHIFT); + x.hi |= BIAS << SHIFT; + return x.x; +} + +double +ldexp(double d, int deltae) +{ + int e, bits; + FPdbleword x; + ulong z; + + if(d == 0) + return 0; + x.x = d; + e = (x.hi >> SHIFT) & MASK; + if(deltae >= 0 || e+deltae >= 1){ /* no underflow */ + e += deltae; + if(e >= MASK){ /* overflow */ + if(d < 0) + return Inf(-1); + return Inf(1); + } + }else{ /* underflow gracefully */ + deltae = -deltae; + /* need to shift d right deltae */ + if(e > 1){ /* shift e-1 by exponent manipulation */ + deltae -= e-1; + e = 1; + } + if(deltae > 0 && e==1){ /* shift 1 by switch from 1.fff to 0.1ff */ + deltae--; + e = 0; + x.lo >>= 1; + x.lo |= (x.hi&1)<<31; + z = x.hi & ((1<<SHIFT)-1); + x.hi &= ~((1<<SHIFT)-1); + x.hi |= (1<<(SHIFT-1)) | (z>>1); + } + while(deltae > 0){ /* shift bits down */ + bits = deltae; + if(bits > SHIFT) + bits = SHIFT; + x.lo >>= bits; + x.lo |= (x.hi&((1<<bits)-1)) << (32-bits); + z = x.hi & ((1<<SHIFT)-1); + x.hi &= ~((1<<SHIFT)-1); + x.hi |= z>>bits; + deltae -= bits; + } + } + x.hi &= ~(MASK << SHIFT); + x.hi |= (long)e << SHIFT; + return x.x; +} + +double +modf(double d, double *ip) +{ + FPdbleword x; + int e; + + if(d < 1) { + if(d < 0) { + x.x = modf(-d, ip); + *ip = -*ip; + return -x.x; + } + *ip = 0; + return d; + } + x.x = d; + e = ((x.hi >> SHIFT) & MASK) - BIAS; + if(e <= SHIFT+1) { + x.hi &= ~(0x1fffffL >> e); + x.lo = 0; + } else + if(e <= SHIFT+33) + x.lo &= ~(0x7fffffffL >> (e-SHIFT-2)); + *ip = x.x; + return d - x.x; +} diff --git a/sys/src/libc/port/getcallerpc.c b/sys/src/libc/port/getcallerpc.c new file mode 100755 index 000000000..f45f8c00c --- /dev/null +++ b/sys/src/libc/port/getcallerpc.c @@ -0,0 +1,8 @@ +#include <u.h> +#include <libc.h> + +uintptr +getcallerpc(void*) +{ + return 0; +} diff --git a/sys/src/libc/port/getfields.c b/sys/src/libc/port/getfields.c new file mode 100755 index 000000000..b12c0cc2b --- /dev/null +++ b/sys/src/libc/port/getfields.c @@ -0,0 +1,37 @@ +#include <u.h> +#include <libc.h> + +int +getfields(char *str, char **args, int max, int mflag, char *set) +{ + Rune r; + int nr, intok, narg; + + if(max <= 0) + return 0; + + narg = 0; + args[narg] = str; + if(!mflag) + narg++; + intok = 0; + for(;; str += nr) { + nr = chartorune(&r, str); + if(r == 0) + break; + if(utfrune(set, r)) { + if(narg >= max) + break; + *str = 0; + intok = 0; + args[narg] = str + nr; + if(!mflag) + narg++; + } else { + if(!intok && mflag) + narg++; + intok = 1; + } + } + return narg; +} diff --git a/sys/src/libc/port/getuser.c b/sys/src/libc/port/getuser.c new file mode 100755 index 000000000..a987244ee --- /dev/null +++ b/sys/src/libc/port/getuser.c @@ -0,0 +1,21 @@ +#include <u.h> +#include <libc.h> + +char * +getuser(void) +{ + static char user[64]; + int fd; + int n; + + fd = open("/dev/user", OREAD); + if(fd < 0) + return "none"; + n = read(fd, user, (sizeof user)-1); + close(fd); + if(n <= 0) + strcpy(user, "none"); + else + user[n] = 0; + return user; +} diff --git a/sys/src/libc/port/hangup.c b/sys/src/libc/port/hangup.c new file mode 100755 index 000000000..83d0735cb --- /dev/null +++ b/sys/src/libc/port/hangup.c @@ -0,0 +1,12 @@ +#include <u.h> +#include <libc.h> +#include <ctype.h> + +/* + * force a connection to hangup + */ +int +hangup(int ctl) +{ + return write(ctl, "hangup", sizeof("hangup")-1) != sizeof("hangup")-1; +} diff --git a/sys/src/libc/port/hypot.c b/sys/src/libc/port/hypot.c new file mode 100755 index 000000000..cb8a33341 --- /dev/null +++ b/sys/src/libc/port/hypot.c @@ -0,0 +1,41 @@ +/* + * hypot -- sqrt(p*p+q*q), but overflows only if the result does. + * See Cleve Moler and Donald Morrison, + * ``Replacing Square Roots by Pythagorean Sums,'' + * IBM Journal of Research and Development, + * Vol. 27, Number 6, pp. 577-581, Nov. 1983 + */ + +#include <u.h> +#include <libc.h> + +double +hypot(double p, double q) +{ + double r, s, pfac; + + if(p < 0) + p = -p; + if(q < 0) + q = -q; + if(p < q) { + r = p; + p = q; + q = r; + } + if(p == 0) + return 0; + pfac = p; + r = q = q/p; + p = 1; + for(;;) { + r *= r; + s = r+4; + if(s == 4) + return p*pfac; + r /= s; + p += 2*r*p; + q *= r; + r = q/p; + } +} diff --git a/sys/src/libc/port/lnrand.c b/sys/src/libc/port/lnrand.c new file mode 100755 index 000000000..5b648d08c --- /dev/null +++ b/sys/src/libc/port/lnrand.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> + +#define MASK 0x7fffffffL + +long +lnrand(long n) +{ + long slop, v; + + if(n < 0) + return n; + slop = MASK % n; + do + v = lrand(); + while(v <= slop); + return v % n; +} diff --git a/sys/src/libc/port/lock.c b/sys/src/libc/port/lock.c new file mode 100755 index 000000000..af07b9cc7 --- /dev/null +++ b/sys/src/libc/port/lock.c @@ -0,0 +1,41 @@ +#include <u.h> +#include <libc.h> + +void +lock(Lock *lk) +{ + int i; + + /* once fast */ + if(!_tas(&lk->val)) + return; + /* a thousand times pretty fast */ + for(i=0; i<1000; i++){ + if(!_tas(&lk->val)) + return; + sleep(0); + } + /* now nice and slow */ + for(i=0; i<1000; i++){ + if(!_tas(&lk->val)) + return; + sleep(100); + } + /* take your time */ + while(_tas(&lk->val)) + sleep(1000); +} + +int +canlock(Lock *lk) +{ + if(_tas(&lk->val)) + return 0; + return 1; +} + +void +unlock(Lock *lk) +{ + lk->val = 0; +} diff --git a/sys/src/libc/port/log.c b/sys/src/libc/port/log.c new file mode 100755 index 000000000..dd84b4cfc --- /dev/null +++ b/sys/src/libc/port/log.c @@ -0,0 +1,58 @@ +/* + log returns the natural logarithm of its floating + point argument. + + The coefficients are #2705 from Hart & Cheney. (19.38D) + + It calls frexp. +*/ + +#include <u.h> +#include <libc.h> + +#define log2 0.693147180559945309e0 +#define ln10o1 .4342944819032518276511 +#define sqrto2 0.707106781186547524e0 +#define p0 -.240139179559210510e2 +#define p1 0.309572928215376501e2 +#define p2 -.963769093377840513e1 +#define p3 0.421087371217979714e0 +#define q0 -.120069589779605255e2 +#define q1 0.194809660700889731e2 +#define q2 -.891110902798312337e1 + +double +log(double arg) +{ + double x, z, zsq, temp; + int exp; + + if(arg <= 0) + return NaN(); + x = frexp(arg, &exp); + while(x < 0.5) { + x *= 2; + exp--; + } + if(x < sqrto2) { + x *= 2; + exp--; + } + + z = (x-1) / (x+1); + zsq = z*z; + + temp = ((p3*zsq + p2)*zsq + p1)*zsq + p0; + temp = temp/(((zsq + q2)*zsq + q1)*zsq + q0); + temp = temp*z + exp*log2; + return temp; +} + +double +log10(double arg) +{ + + if(arg <= 0) + return NaN(); + return log(arg) * ln10o1; +} diff --git a/sys/src/libc/port/lrand.c b/sys/src/libc/port/lrand.c new file mode 100755 index 000000000..2ebb39622 --- /dev/null +++ b/sys/src/libc/port/lrand.c @@ -0,0 +1,83 @@ +#include <u.h> +#include <libc.h> + +/* + * algorithm by + * D. P. Mitchell & J. A. Reeds + */ + +#define LEN 607 +#define TAP 273 +#define MASK 0x7fffffffL +#define A 48271 +#define M 2147483647 +#define Q 44488 +#define R 3399 +#define NORM (1.0/(1.0+MASK)) + +static ulong rng_vec[LEN]; +static ulong* rng_tap = rng_vec; +static ulong* rng_feed = 0; +static Lock lk; + +static void +isrand(long seed) +{ + long lo, hi, x; + int i; + + rng_tap = rng_vec; + rng_feed = rng_vec+LEN-TAP; + seed = seed%M; + if(seed < 0) + seed += M; + if(seed == 0) + seed = 89482311; + x = seed; + /* + * Initialize by x[n+1] = 48271 * x[n] mod (2**31 - 1) + */ + for(i = -20; i < LEN; i++) { + hi = x / Q; + lo = x % Q; + x = A*lo - R*hi; + if(x < 0) + x += M; + if(i >= 0) + rng_vec[i] = x; + } +} + +void +srand(long seed) +{ + lock(&lk); + isrand(seed); + unlock(&lk); +} + +long +lrand(void) +{ + ulong x; + + lock(&lk); + + rng_tap--; + if(rng_tap < rng_vec) { + if(rng_feed == 0) { + isrand(1); + rng_tap--; + } + rng_tap += LEN; + } + rng_feed--; + if(rng_feed < rng_vec) + rng_feed += LEN; + x = (*rng_feed + *rng_tap) & MASK; + *rng_feed = x; + + unlock(&lk); + + return x; +} diff --git a/sys/src/libc/port/malloc.acid b/sys/src/libc/port/malloc.acid new file mode 100755 index 000000000..514bb8d98 --- /dev/null +++ b/sys/src/libc/port/malloc.acid @@ -0,0 +1,366 @@ +sizeof_1_ = 8; +aggr _1_ +{ + 'D' 0 lo; + 'D' 4 hi; +}; + +defn +_1_(addr) { + complex _1_ addr; + print(" lo ", addr.lo, "\n"); + print(" hi ", addr.hi, "\n"); +}; + +sizeofFPdbleword = 8; +aggr FPdbleword +{ + 'F' 0 x; + { + 'D' 0 lo; + 'D' 4 hi; + }; +}; + +defn +FPdbleword(addr) { + complex FPdbleword addr; + print(" x ", addr.x, "\n"); + print("_1_ {\n"); + _1_(addr+0); + print("}\n"); +}; + +UTFmax = 3; +Runesync = 128; +Runeself = 128; +Runeerror = 128; +sizeofFconv = 24; +aggr Fconv +{ + 'X' 0 out; + 'X' 4 eout; + 'D' 8 f1; + 'D' 12 f2; + 'D' 16 f3; + 'D' 20 chr; +}; + +defn +Fconv(addr) { + complex Fconv addr; + print(" out ", addr.out\X, "\n"); + print(" eout ", addr.eout\X, "\n"); + print(" f1 ", addr.f1, "\n"); + print(" f2 ", addr.f2, "\n"); + print(" f3 ", addr.f3, "\n"); + print(" chr ", addr.chr, "\n"); +}; + +sizeofTm = 40; +aggr Tm +{ + 'D' 0 sec; + 'D' 4 min; + 'D' 8 hour; + 'D' 12 mday; + 'D' 16 mon; + 'D' 20 year; + 'D' 24 wday; + 'D' 28 yday; + 'a' 32 zone; + 'D' 36 tzoff; +}; + +defn +Tm(addr) { + complex Tm addr; + print(" sec ", addr.sec, "\n"); + print(" min ", addr.min, "\n"); + print(" hour ", addr.hour, "\n"); + print(" mday ", addr.mday, "\n"); + print(" mon ", addr.mon, "\n"); + print(" year ", addr.year, "\n"); + print(" wday ", addr.wday, "\n"); + print(" yday ", addr.yday, "\n"); + print(" zone ", addr.zone, "\n"); + print(" tzoff ", addr.tzoff, "\n"); +}; + +PNPROC = 1; +PNGROUP = 2; +sizeofLock = 4; +aggr Lock +{ + 'D' 0 val; +}; + +defn +Lock(addr) { + complex Lock addr; + print(" val ", addr.val, "\n"); +}; + +sizeofQLp = 12; +aggr QLp +{ + 'D' 0 inuse; + 'A' QLp 4 next; + 'C' 8 state; +}; + +defn +QLp(addr) { + complex QLp addr; + print(" inuse ", addr.inuse, "\n"); + print(" next ", addr.next\X, "\n"); + print(" state ", addr.state, "\n"); +}; + +sizeofQLock = 16; +aggr QLock +{ + Lock 0 lock; + 'D' 4 locked; + 'A' QLp 8 $head; + 'A' QLp 12 $tail; +}; + +defn +QLock(addr) { + complex QLock addr; + print("Lock lock {\n"); + Lock(addr.lock); + print("}\n"); + print(" locked ", addr.locked, "\n"); + print(" $head ", addr.$head\X, "\n"); + print(" $tail ", addr.$tail\X, "\n"); +}; + +sizeofRWLock = 20; +aggr RWLock +{ + Lock 0 lock; + 'D' 4 readers; + 'D' 8 writer; + 'A' QLp 12 $head; + 'A' QLp 16 $tail; +}; + +defn +RWLock(addr) { + complex RWLock addr; + print("Lock lock {\n"); + Lock(addr.lock); + print("}\n"); + print(" readers ", addr.readers, "\n"); + print(" writer ", addr.writer, "\n"); + print(" $head ", addr.$head\X, "\n"); + print(" $tail ", addr.$tail\X, "\n"); +}; + +RFNAMEG = 1; +RFENVG = 2; +RFFDG = 4; +RFNOTEG = 8; +RFPROC = 16; +RFMEM = 32; +RFNOWAIT = 64; +RFCNAMEG = 1024; +RFCENVG = 2048; +RFCFDG = 4096; +RFREND = 8192; +RFNOMNT = 16384; +sizeofQid = 16; +aggr Qid +{ + 'W' 0 path; + 'U' 8 vers; + 'b' 12 type; +}; + +defn +Qid(addr) { + complex Qid addr; + print(" path ", addr.path, "\n"); + print(" vers ", addr.vers, "\n"); + print(" type ", addr.type, "\n"); +}; + +sizeofDir = 60; +aggr Dir +{ + 'u' 0 type; + 'U' 4 dev; + Qid 8 qid; + 'U' 24 mode; + 'U' 28 atime; + 'U' 32 mtime; + 'V' 36 length; + 'X' 44 name; + 'X' 48 uid; + 'X' 52 gid; + 'X' 56 muid; +}; + +defn +Dir(addr) { + complex Dir addr; + print(" type ", addr.type, "\n"); + print(" dev ", addr.dev, "\n"); + print("Qid qid {\n"); + Qid(addr.qid); + print("}\n"); + print(" mode ", addr.mode, "\n"); + print(" atime ", addr.atime, "\n"); + print(" mtime ", addr.mtime, "\n"); + print(" length ", addr.length, "\n"); + print(" name ", addr.name\X, "\n"); + print(" uid ", addr.uid\X, "\n"); + print(" gid ", addr.gid\X, "\n"); + print(" muid ", addr.muid\X, "\n"); +}; + +sizeofWaitmsg = 20; +aggr Waitmsg +{ + 'D' 0 pid; + 'a' 4 time; + 'X' 16 msg; +}; + +defn +Waitmsg(addr) { + complex Waitmsg addr; + print(" pid ", addr.pid, "\n"); + print(" time ", addr.time, "\n"); + print(" msg ", addr.msg\X, "\n"); +}; + +sizeofIOchunk = 8; +aggr IOchunk +{ + 'X' 0 addr; + 'U' 4 len; +}; + +defn +IOchunk(addr) { + complex IOchunk addr; + print(" addr ", addr.addr\X, "\n"); + print(" len ", addr.len, "\n"); +}; + +sizeofPool = 88; +aggr Pool +{ + 'X' 0 name; + 'U' 4 maxsize; + 'U' 8 cursize; + 'U' 12 curfree; + 'U' 16 curalloc; + 'U' 20 minarena; + 'U' 24 quantum; + 'U' 28 minblock; + 'X' 32 freeroot; + 'X' 36 arenalist; + 'X' 40 alloc; + 'X' 44 merge; + 'X' 48 move; + 'D' 52 flags; + 'D' 56 nfree; + 'D' 60 lastcompact; + 'X' 64 lock; + 'X' 68 unlock; + 'X' 72 print; + 'X' 76 panic; + 'X' 80 logstack; + 'X' 84 private; +}; + +defn +Pool(addr) { + complex Pool addr; + print(" name ", addr.name\X, "\n"); + print(" maxsize ", addr.maxsize, "\n"); + print(" cursize ", addr.cursize, "\n"); + print(" curfree ", addr.curfree, "\n"); + print(" curalloc ", addr.curalloc, "\n"); + print(" minarena ", addr.minarena, "\n"); + print(" quantum ", addr.quantum, "\n"); + print(" minblock ", addr.minblock, "\n"); + print(" freeroot ", addr.freeroot\X, "\n"); + print(" arenalist ", addr.arenalist\X, "\n"); + print(" alloc ", addr.alloc\X, "\n"); + print(" merge ", addr.merge\X, "\n"); + print(" move ", addr.move\X, "\n"); + print(" flags ", addr.flags, "\n"); + print(" nfree ", addr.nfree, "\n"); + print(" lastcompact ", addr.lastcompact, "\n"); + print(" lock ", addr.lock\X, "\n"); + print(" unlock ", addr.unlock\X, "\n"); + print(" print ", addr.print\X, "\n"); + print(" panic ", addr.panic\X, "\n"); + print(" logstack ", addr.logstack\X, "\n"); + print(" private ", addr.private\X, "\n"); +}; + +sizeofTraverse = 20; +aggr Traverse +{ + 'X' 0 visit; + 'D' 4 maxvisit; + 'X' 8 a; + 'X' 12 b; + 'X' 16 prev; +}; + +defn +Traverse(addr) { + complex Traverse addr; + print(" visit ", addr.visit\X, "\n"); + print(" maxvisit ", addr.maxvisit, "\n"); + print(" a ", addr.a\X, "\n"); + print(" b ", addr.b\X, "\n"); + print(" prev ", addr.prev\X, "\n"); +}; + +complex Pool mainmem; +complex Pool imagmem; +POOL_ANTAGONISM = 1; +POOL_PARANOIA = 2; +POOL_VERBOSITY = 4; +POOL_DEBUGGING = 8; +POOL_LOGGING = 16; +POOL_TOLERANCE = 32; +sizeofPrivate = 8; +aggr Private +{ + Lock 0 lk; + 'D' 4 printfd; +}; + +defn +Private(addr) { + complex Private addr; + print("Lock lk {\n"); + Lock(addr.lk); + print("}\n"); + print(" printfd ", addr.printfd, "\n"); +}; + +complex Private sbrkmempriv; +complex Pool sbrkmem; +complex Pool mainmem; +complex Pool imagmem; +complex Pool plock:p; +complex Private plock:pv; +complex Pool punlock:p; +complex Private punlock:pv; +complex Pool pprint:p; +complex Private pprint:pv; +complex Pool ppanic:p; +complex Private ppanic:pv; +Npadlong = 2; +MallocOffset = 0; +ReallocOffset = 1; diff --git a/sys/src/libc/port/malloc.c b/sys/src/libc/port/malloc.c new file mode 100755 index 000000000..741316926 --- /dev/null +++ b/sys/src/libc/port/malloc.c @@ -0,0 +1,338 @@ +#include <u.h> +#include <libc.h> +#include <pool.h> +#include <tos.h> + +static void* sbrkalloc(ulong); +static int sbrkmerge(void*, void*); +static void plock(Pool*); +static void punlock(Pool*); +static void pprint(Pool*, char*, ...); +static void ppanic(Pool*, char*, ...); + +typedef struct Private Private; +struct Private { + Lock lk; + int pid; + int printfd; /* gets debugging output if set */ +}; + +Private sbrkmempriv; + +static Pool sbrkmem = { + .name= "sbrkmem", + .maxsize= (3840UL-1)*1024*1024, /* up to ~0xf0000000 */ + .minarena= 4*1024, + .quantum= 32, + .alloc= sbrkalloc, + .merge= sbrkmerge, + .flags= 0, + + .lock= plock, + .unlock= punlock, + .print= pprint, + .panic= ppanic, + .private= &sbrkmempriv, +}; +Pool *mainmem = &sbrkmem; +Pool *imagmem = &sbrkmem; + +/* + * we do minimal bookkeeping so we can tell pool + * whether two blocks are adjacent and thus mergeable. + */ +static void* +sbrkalloc(ulong n) +{ + ulong *x; + + n += 2*sizeof(ulong); /* two longs for us */ + x = sbrk(n); + if(x == (void*)-1) + return nil; + x[0] = (n+7)&~7; /* sbrk rounds size up to mult. of 8 */ + x[1] = 0xDeadBeef; + return x+2; +} + +static int +sbrkmerge(void *x, void *y) +{ + ulong *lx, *ly; + + lx = x; + if(lx[-1] != 0xDeadBeef) + abort(); + + if((uchar*)lx+lx[-2] == (uchar*)y) { + ly = y; + lx[-2] += ly[-2]; + return 1; + } + return 0; +} + +static void +plock(Pool *p) +{ + Private *pv; + pv = p->private; + lock(&pv->lk); + if(pv->pid != 0) + abort(); + pv->pid = _tos->pid; +} + +static void +punlock(Pool *p) +{ + Private *pv; + pv = p->private; + if(pv->pid != _tos->pid) + abort(); + pv->pid = 0; + unlock(&pv->lk); +} + +static int +checkenv(void) +{ + int n, fd; + char buf[20]; + fd = open("/env/MALLOCFD", OREAD); + if(fd < 0) + return -1; + if((n = read(fd, buf, sizeof buf)) < 0) { + close(fd); + return -1; + } + if(n >= sizeof buf) + n = sizeof(buf)-1; + buf[n] = 0; + n = atoi(buf); + if(n == 0) + n = -1; + return n; +} + +static void +pprint(Pool *p, char *fmt, ...) +{ + va_list v; + Private *pv; + + pv = p->private; + if(pv->printfd == 0) + pv->printfd = checkenv(); + + if(pv->printfd <= 0) + pv->printfd = 2; + + va_start(v, fmt); + vfprint(pv->printfd, fmt, v); + va_end(v); +} + +static char panicbuf[256]; +static void +ppanic(Pool *p, char *fmt, ...) +{ + va_list v; + int n; + char *msg; + Private *pv; + + pv = p->private; + assert(canlock(&pv->lk)==0); + + if(pv->printfd == 0) + pv->printfd = checkenv(); + if(pv->printfd <= 0) + pv->printfd = 2; + + msg = panicbuf; + va_start(v, fmt); + n = vseprint(msg, msg+sizeof panicbuf, fmt, v) - msg; + write(2, "panic: ", 7); + write(2, msg, n); + write(2, "\n", 1); + if(pv->printfd != 2){ + write(pv->printfd, "panic: ", 7); + write(pv->printfd, msg, n); + write(pv->printfd, "\n", 1); + } + va_end(v); +// unlock(&pv->lk); + abort(); +} + +/* - everything from here down should be the same in libc, libdebugmalloc, and the kernel - */ +/* - except the code for malloc(), which alternately doesn't clear or does. - */ + +/* + * Npadlong is the number of 32-bit longs to leave at the beginning of + * each allocated buffer for our own bookkeeping. We return to the callers + * a pointer that points immediately after our bookkeeping area. Incoming pointers + * must be decremented by that much, and outgoing pointers incremented. + * The malloc tag is stored at MallocOffset from the beginning of the block, + * and the realloc tag at ReallocOffset. The offsets are from the true beginning + * of the block, not the beginning the caller sees. + * + * The extra if(Npadlong != 0) in various places is a hint for the compiler to + * compile out function calls that would otherwise be no-ops. + */ + +/* non tracing + * +enum { + Npadlong = 0, + MallocOffset = 0, + ReallocOffset = 0, +}; + * + */ + +/* tracing */ +enum { + Npadlong = 2, + MallocOffset = 0, + ReallocOffset = 1 +}; + +void* +malloc(ulong size) +{ + void *v; + + v = poolalloc(mainmem, size+Npadlong*sizeof(ulong)); + if(Npadlong && v != nil) { + v = (ulong*)v+Npadlong; + setmalloctag(v, getcallerpc(&size)); + setrealloctag(v, 0); + } + return v; +} + +void* +mallocz(ulong size, int clr) +{ + void *v; + + v = poolalloc(mainmem, size+Npadlong*sizeof(ulong)); + if(Npadlong && v != nil){ + v = (ulong*)v+Npadlong; + setmalloctag(v, getcallerpc(&size)); + setrealloctag(v, 0); + } + if(clr && v != nil) + memset(v, 0, size); + return v; +} + +void* +mallocalign(ulong size, ulong align, long offset, ulong span) +{ + void *v; + + v = poolallocalign(mainmem, size+Npadlong*sizeof(ulong), align, offset-Npadlong*sizeof(ulong), span); + if(Npadlong && v != nil){ + v = (ulong*)v+Npadlong; + setmalloctag(v, getcallerpc(&size)); + setrealloctag(v, 0); + } + return v; +} + +void +free(void *v) +{ + if(v != nil) + poolfree(mainmem, (ulong*)v-Npadlong); +} + +void* +realloc(void *v, ulong size) +{ + void *nv; + + if(size == 0){ + free(v); + return nil; + } + + if(v) + v = (ulong*)v-Npadlong; + size += Npadlong*sizeof(ulong); + + if(nv = poolrealloc(mainmem, v, size)){ + nv = (ulong*)nv+Npadlong; + setrealloctag(nv, getcallerpc(&v)); + if(v == nil) + setmalloctag(nv, getcallerpc(&v)); + } + return nv; +} + +ulong +msize(void *v) +{ + return poolmsize(mainmem, (ulong*)v-Npadlong)-Npadlong*sizeof(ulong); +} + +void* +calloc(ulong n, ulong szelem) +{ + void *v; + if(v = mallocz(n*szelem, 1)) + setmalloctag(v, getcallerpc(&n)); + return v; +} + +void +setmalloctag(void *v, ulong pc) +{ + ulong *u; + USED(v, pc); + if(Npadlong <= MallocOffset || v == nil) + return; + u = v; + u[-Npadlong+MallocOffset] = pc; +} + +void +setrealloctag(void *v, ulong pc) +{ + ulong *u; + USED(v, pc); + if(Npadlong <= ReallocOffset || v == nil) + return; + u = v; + u[-Npadlong+ReallocOffset] = pc; +} + +ulong +getmalloctag(void *v) +{ + USED(v); + if(Npadlong <= MallocOffset) + return ~0; + return ((ulong*)v)[-Npadlong+MallocOffset]; +} + +ulong +getrealloctag(void *v) +{ + USED(v); + if(Npadlong <= ReallocOffset) + return ((ulong*)v)[-Npadlong+ReallocOffset]; + return ~0; +} + +void* +malloctopoolblock(void *v) +{ + if(v == nil) + return nil; + + return &((ulong*)v)[-Npadlong]; +} diff --git a/sys/src/libc/port/memccpy.c b/sys/src/libc/port/memccpy.c new file mode 100755 index 000000000..9268ba72e --- /dev/null +++ b/sys/src/libc/port/memccpy.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> + +void* +memccpy(void *a1, void *a2, int c, ulong n) +{ + uchar *s1, *s2; + + s1 = a1; + s2 = a2; + c &= 0xFF; + while(n > 0) { + if((*s1++ = *s2++) == c) + return s1; + n--; + } + return 0; +} diff --git a/sys/src/libc/port/memchr.c b/sys/src/libc/port/memchr.c new file mode 100755 index 000000000..fb4b1d148 --- /dev/null +++ b/sys/src/libc/port/memchr.c @@ -0,0 +1,17 @@ +#include <u.h> +#include <libc.h> + +void* +memchr(void *ap, int c, ulong n) +{ + uchar *sp; + + sp = ap; + c &= 0xFF; + while(n > 0) { + if(*sp++ == c) + return sp-1; + n--; + } + return 0; +} diff --git a/sys/src/libc/port/memcmp.c b/sys/src/libc/port/memcmp.c new file mode 100755 index 000000000..211752b03 --- /dev/null +++ b/sys/src/libc/port/memcmp.c @@ -0,0 +1,23 @@ +#include <u.h> +#include <libc.h> + +int +memcmp(void *a1, void *a2, ulong n) +{ + uchar *s1, *s2; + uint c1, c2; + + s1 = a1; + s2 = a2; + while(n > 0) { + c1 = *s1++; + c2 = *s2++; + if(c1 != c2) { + if(c1 > c2) + return 1; + return -1; + } + n--; + } + return 0; +} diff --git a/sys/src/libc/port/memmove.c b/sys/src/libc/port/memmove.c new file mode 100755 index 000000000..16ef43277 --- /dev/null +++ b/sys/src/libc/port/memmove.c @@ -0,0 +1,35 @@ +#include <u.h> +#include <libc.h> + +void* +memmove(void *a1, void *a2, ulong n) +{ + char *s1, *s2; + + if((long)n < 0) + abort(); + s1 = a1; + s2 = a2; + if((s2 < s1) && (s2+n > s1)) + goto back; + while(n > 0) { + *s1++ = *s2++; + n--; + } + return a1; + +back: + s1 += n; + s2 += n; + while(n > 0) { + *--s1 = *--s2; + n--; + } + return a1; +} + +void* +memcpy(void *a1, void *a2, ulong n) +{ + return memmove(a1, a2, n); +} diff --git a/sys/src/libc/port/memset.c b/sys/src/libc/port/memset.c new file mode 100755 index 000000000..431d6bb30 --- /dev/null +++ b/sys/src/libc/port/memset.c @@ -0,0 +1,15 @@ +#include <u.h> +#include <libc.h> + +void* +memset(void *ap, int c, ulong n) +{ + char *p; + + p = ap; + while(n > 0) { + *p++ = c; + n--; + } + return ap; +} diff --git a/sys/src/libc/port/mkfile b/sys/src/libc/port/mkfile new file mode 100755 index 000000000..dc2d93694 --- /dev/null +++ b/sys/src/libc/port/mkfile @@ -0,0 +1,127 @@ +</$objtype/mkfile + +LIB=/$objtype/lib/libc.a +CFILES=\ + _assert.c\ + abs.c\ + asin.c\ + atan.c\ + atan2.c\ + atexit.c\ + atnotify.c\ + atof.c\ + atol.c\ + atoll.c\ + cistrcmp.c\ + cistrncmp.c\ + cistrstr.c\ + charstod.c\ + cleanname.c\ + crypt.c\ + ctype.c\ + encodefmt.c\ + execl.c\ + exp.c\ + fabs.c\ + floor.c\ + fmod.c\ + frand.c\ + frexp.c\ + getcallerpc.c\ + getfields.c\ + getuser.c\ + hangup.c\ + hypot.c\ + lnrand.c\ + lock.c\ + log.c\ + lrand.c\ + malloc.c\ + memccpy.c\ + memchr.c\ + memcmp.c\ + memmove.c\ + memset.c\ + mktemp.c\ + muldiv.c\ + nan.c\ + needsrcquote.c\ + netcrypt.c\ + netmkaddr.c\ + nrand.c\ + ntruerand.c\ + perror.c\ + pool.c\ + pow.c\ + pow10.c\ + profile.c\ + qsort.c\ + quote.c\ + rand.c\ + readn.c\ + rune.c\ + runestrcat.c\ + runestrchr.c\ + runestrcmp.c\ + runestrcpy.c\ + runestrecpy.c\ + runestrdup.c\ + runestrncat.c\ + runestrncmp.c\ + runestrncpy.c\ + runestrrchr.c\ + runestrlen.c\ + runestrstr.c\ + runetype.c\ + sin.c\ + sinh.c\ + sqrt.c\ + strcat.c\ + strchr.c\ + strcmp.c\ + strcpy.c\ + strecpy.c\ + strcspn.c\ + strdup.c\ + strlen.c\ + strncat.c\ + strncmp.c\ + strncpy.c\ + strpbrk.c\ + strrchr.c\ + strspn.c\ + strstr.c\ + strtod.c\ + strtok.c\ + strtol.c\ + strtoll.c\ + strtoul.c\ + strtoull.c\ + tan.c\ + tanh.c\ + tokenize.c\ + toupper.c\ + utfecpy.c\ + utflen.c\ + utfnlen.c\ + utfrune.c\ + utfrrune.c\ + utfutf.c\ + u16.c\ + u32.c\ + u64.c\ + +ALLOFILES=${CFILES:%.c=%.$O} + +# cull things in the per-machine directories from this list +OFILES= `{rc ./reduce $O $objtype $ALLOFILES} + +HFILES=/sys/include/libc.h + +UPDATE=mkfile\ + $HFILES\ + $CFILES\ + +</sys/src/cmd/mksyslib + +profile.$O: /sys/include/tos.h diff --git a/sys/src/libc/port/mktemp.c b/sys/src/libc/port/mktemp.c new file mode 100755 index 000000000..384d7fcf7 --- /dev/null +++ b/sys/src/libc/port/mktemp.c @@ -0,0 +1,31 @@ +#include <u.h> +#include <libc.h> + +char* +mktemp(char *as) +{ + char *s; + unsigned pid; + int i; + char err[ERRMAX]; + + pid = getpid(); + s = as; + while(*s++) + ; + s--; + while(*--s == 'X') { + *s = pid % 10 + '0'; + pid = pid/10; + } + s++; + i = 'a'; + while(access(as, 0) != -1) { + if (i == 'z') + return "/"; + *s = i++; + } + err[0] = '\0'; + errstr(err, sizeof err); /* clear the error */ + return as; +} diff --git a/sys/src/libc/port/muldiv.c b/sys/src/libc/port/muldiv.c new file mode 100755 index 000000000..c304daf6e --- /dev/null +++ b/sys/src/libc/port/muldiv.c @@ -0,0 +1,38 @@ +#include <u.h> +#include <libc.h> + +ulong +umuldiv(ulong a, ulong b, ulong c) +{ + double d; + + d = ((double)a * (double)b) / (double)c; + if(d >= 4294967296.) + abort(); + return d; +} + +long +muldiv(long a, long b, long c) +{ + int s; + long v; + + s = 0; + if(a < 0) { + s = !s; + a = -a; + } + if(b < 0) { + s = !s; + b = -b; + } + if(c < 0) { + s = !s; + c = -c; + } + v = umuldiv(a, b, c); + if(s) + v = -v; + return v; +} diff --git a/sys/src/libc/port/nan.c b/sys/src/libc/port/nan.c new file mode 100755 index 000000000..f5a4cec34 --- /dev/null +++ b/sys/src/libc/port/nan.c @@ -0,0 +1,54 @@ +#include <u.h> +#include <libc.h> + +#define NANEXP (2047<<20) +#define NANMASK (2047<<20) +#define NANSIGN (1<<31) + +double +NaN(void) +{ + FPdbleword a; + + a.hi = NANEXP; + a.lo = 1; + return a.x; +} + +int +isNaN(double d) +{ + FPdbleword a; + + a.x = d; + if((a.hi & NANMASK) != NANEXP) + return 0; + return !isInf(d, 0); +} + +double +Inf(int sign) +{ + FPdbleword a; + + a.hi = NANEXP; + a.lo = 0; + if(sign < 0) + a.hi |= NANSIGN; + return a.x; +} + +int +isInf(double d, int sign) +{ + FPdbleword a; + + a.x = d; + if(a.lo != 0) + return 0; + if(a.hi == NANEXP) + return sign >= 0; + if(a.hi == (NANEXP|NANSIGN)) + return sign <= 0; + return 0; +} diff --git a/sys/src/libc/port/needsrcquote.c b/sys/src/libc/port/needsrcquote.c new file mode 100755 index 000000000..f211ea1f9 --- /dev/null +++ b/sys/src/libc/port/needsrcquote.c @@ -0,0 +1,12 @@ +#include <u.h> +#include <libc.h> + +int +needsrcquote(int c) +{ + if(c <= ' ') + return 1; + if(utfrune("`^#*[]=|\\?${}()'<>&;", c)) + return 1; + return 0; +} diff --git a/sys/src/libc/port/netcrypt.c b/sys/src/libc/port/netcrypt.c new file mode 100755 index 000000000..08fa6761c --- /dev/null +++ b/sys/src/libc/port/netcrypt.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> +#include <auth.h> + +int +netcrypt(void *key, void *chal) +{ + uchar buf[8], *p; + + strncpy((char*)buf, chal, 7); + buf[7] = '\0'; + for(p = buf; *p && *p != '\n'; p++) + ; + *p = '\0'; + encrypt(key, buf, 8); + sprint(chal, "%.2ux%.2ux%.2ux%.2ux", buf[0], buf[1], buf[2], buf[3]); + return 1; +} diff --git a/sys/src/libc/port/netmkaddr.c b/sys/src/libc/port/netmkaddr.c new file mode 100755 index 000000000..fd53f4684 --- /dev/null +++ b/sys/src/libc/port/netmkaddr.c @@ -0,0 +1,52 @@ +#include <u.h> +#include <libc.h> +#include <ctype.h> + +/* + * make an address, add the defaults + */ +char * +netmkaddr(char *linear, char *defnet, char *defsrv) +{ + static char addr[256]; + char *cp; + + /* + * dump network name + */ + cp = strchr(linear, '!'); + if(cp == 0){ + if(defnet==0){ + if(defsrv) + snprint(addr, sizeof(addr), "net!%s!%s", + linear, defsrv); + else + snprint(addr, sizeof(addr), "net!%s", linear); + } + else { + if(defsrv) + snprint(addr, sizeof(addr), "%s!%s!%s", defnet, + linear, defsrv); + else + snprint(addr, sizeof(addr), "%s!%s", defnet, + linear); + } + return addr; + } + + /* + * if there is already a service, use it + */ + cp = strchr(cp+1, '!'); + if(cp) + return linear; + + /* + * add default service + */ + if(defsrv == 0) + return linear; + snprint(addr, sizeof(addr), "%s!%s", linear, defsrv); + + return addr; +} diff --git a/sys/src/libc/port/nrand.c b/sys/src/libc/port/nrand.c new file mode 100755 index 000000000..31dbe27ff --- /dev/null +++ b/sys/src/libc/port/nrand.c @@ -0,0 +1,21 @@ +#include <u.h> +#include <libc.h> + +#define MASK 0x7fffffffL + +int +nrand(int n) +{ + long slop, v; + + if(n < 0) + return n; + if(n == 1) + return 0; + /* and if n == 0, you deserve what you get */ + slop = MASK % n; + do + v = lrand(); + while(v <= slop); + return v % n; +} diff --git a/sys/src/libc/port/ntruerand.c b/sys/src/libc/port/ntruerand.c new file mode 100755 index 000000000..248eda647 --- /dev/null +++ b/sys/src/libc/port/ntruerand.c @@ -0,0 +1,23 @@ +#include <u.h> +#include <libc.h> + +ulong +ntruerand(ulong n) +{ + ulong m, r; + + /* + * set m to the one less than the maximum multiple of n <= 2^32, + * so we want a random number <= m. + */ + if(n > (1UL<<31)) + m = n-1; + else + /* 2^32 - 2^32%n - 1 = (2^32 - 1) - (2*(2^31%n))%n */ + m = 0xFFFFFFFFUL - (2*((1UL<<31)%n))%n; + + while((r = truerand()) > m) + ; + + return r%n; +} diff --git a/sys/src/libc/port/perror.c b/sys/src/libc/port/perror.c new file mode 100755 index 000000000..c4c03c7bc --- /dev/null +++ b/sys/src/libc/port/perror.c @@ -0,0 +1,15 @@ +#include <u.h> +#include <libc.h> + +void +perror(char *s) +{ + char buf[ERRMAX]; + + buf[0] = '\0'; + errstr(buf, sizeof buf); + if(s && *s) + fprint(2, "%s: %s\n", s, buf); + else + fprint(2, "%s\n", buf); +} diff --git a/sys/src/libc/port/pool.acid b/sys/src/libc/port/pool.acid new file mode 100755 index 000000000..da58aa441 --- /dev/null +++ b/sys/src/libc/port/pool.acid @@ -0,0 +1,628 @@ +sizeof_1_ = 8; +aggr _1_ +{ + 'U' 0 lo; + 'U' 4 hi; +}; + +defn +_1_(addr) { + complex _1_ addr; + print(" lo ", addr.lo, "\n"); + print(" hi ", addr.hi, "\n"); +}; + +sizeofFPdbleword = 8; +aggr FPdbleword +{ + 'F' 0 x; + { + 'U' 0 lo; + 'U' 4 hi; + }; +}; + +defn +FPdbleword(addr) { + complex FPdbleword addr; + print(" x ", addr.x, "\n"); + print("_1_ {\n"); + _1_(addr+0); + print("}\n"); +}; + +UTFmax = 3; +Runesync = 128; +Runeself = 128; +Runeerror = 65533; +sizeofFmt = 48; +aggr Fmt +{ + 'b' 0 runes; + 'X' 4 start; + 'X' 8 to; + 'X' 12 stop; + 'X' 16 flush; + 'X' 20 farg; + 'D' 24 nfmt; + 'X' 28 args; + 'D' 32 r; + 'D' 36 width; + 'D' 40 prec; + 'U' 44 flags; +}; + +defn +Fmt(addr) { + complex Fmt addr; + print(" runes ", addr.runes, "\n"); + print(" start ", addr.start\X, "\n"); + print(" to ", addr.to\X, "\n"); + print(" stop ", addr.stop\X, "\n"); + print(" flush ", addr.flush\X, "\n"); + print(" farg ", addr.farg\X, "\n"); + print(" nfmt ", addr.nfmt, "\n"); + print(" args ", addr.args\X, "\n"); + print(" r ", addr.r, "\n"); + print(" width ", addr.width, "\n"); + print(" prec ", addr.prec, "\n"); + print(" flags ", addr.flags, "\n"); +}; + +FmtWidth = 1; +FmtLeft = 2; +FmtPrec = 4; +FmtSharp = 8; +FmtSpace = 16; +FmtSign = 32; +FmtZero = 64; +FmtUnsigned = 128; +FmtShort = 256; +FmtLong = 512; +FmtVLong = 1024; +FmtComma = 2048; +FmtByte = 4096; +FmtFlag = 8192; +sizeofTm = 40; +aggr Tm +{ + 'D' 0 sec; + 'D' 4 min; + 'D' 8 hour; + 'D' 12 mday; + 'D' 16 mon; + 'D' 20 year; + 'D' 24 wday; + 'D' 28 yday; + 'a' 32 zone; + 'D' 36 tzoff; +}; + +defn +Tm(addr) { + complex Tm addr; + print(" sec ", addr.sec, "\n"); + print(" min ", addr.min, "\n"); + print(" hour ", addr.hour, "\n"); + print(" mday ", addr.mday, "\n"); + print(" mon ", addr.mon, "\n"); + print(" year ", addr.year, "\n"); + print(" wday ", addr.wday, "\n"); + print(" yday ", addr.yday, "\n"); + print(" zone ", addr.zone, "\n"); + print(" tzoff ", addr.tzoff, "\n"); +}; + +PNPROC = 1; +PNGROUP = 2; +Profoff = 0; +Profuser = 1; +Profkernel = 2; +Proftime = 3; +Profsample = 4; +sizeofLock = 4; +aggr Lock +{ + 'D' 0 val; +}; + +defn +Lock(addr) { + complex Lock addr; + print(" val ", addr.val, "\n"); +}; + +sizeofQLp = 12; +aggr QLp +{ + 'D' 0 inuse; + 'A' QLp 4 next; + 'C' 8 state; +}; + +defn +QLp(addr) { + complex QLp addr; + print(" inuse ", addr.inuse, "\n"); + print(" next ", addr.next\X, "\n"); + print(" state ", addr.state, "\n"); +}; + +sizeofQLock = 16; +aggr QLock +{ + Lock 0 lock; + 'D' 4 locked; + 'A' QLp 8 $head; + 'A' QLp 12 $tail; +}; + +defn +QLock(addr) { + complex QLock addr; + print("Lock lock {\n"); + Lock(addr.lock); + print("}\n"); + print(" locked ", addr.locked, "\n"); + print(" $head ", addr.$head\X, "\n"); + print(" $tail ", addr.$tail\X, "\n"); +}; + +sizeofRWLock = 20; +aggr RWLock +{ + Lock 0 lock; + 'D' 4 readers; + 'D' 8 writer; + 'A' QLp 12 $head; + 'A' QLp 16 $tail; +}; + +defn +RWLock(addr) { + complex RWLock addr; + print("Lock lock {\n"); + Lock(addr.lock); + print("}\n"); + print(" readers ", addr.readers, "\n"); + print(" writer ", addr.writer, "\n"); + print(" $head ", addr.$head\X, "\n"); + print(" $tail ", addr.$tail\X, "\n"); +}; + +sizeofRendez = 12; +aggr Rendez +{ + 'A' QLock 0 l; + 'A' QLp 4 $head; + 'A' QLp 8 $tail; +}; + +defn +Rendez(addr) { + complex Rendez addr; + print(" l ", addr.l\X, "\n"); + print(" $head ", addr.$head\X, "\n"); + print(" $tail ", addr.$tail\X, "\n"); +}; + +sizeofNetConnInfo = 36; +aggr NetConnInfo +{ + 'X' 0 dir; + 'X' 4 root; + 'X' 8 spec; + 'X' 12 lsys; + 'X' 16 lserv; + 'X' 20 rsys; + 'X' 24 rserv; + 'X' 28 laddr; + 'X' 32 raddr; +}; + +defn +NetConnInfo(addr) { + complex NetConnInfo addr; + print(" dir ", addr.dir\X, "\n"); + print(" root ", addr.root\X, "\n"); + print(" spec ", addr.spec\X, "\n"); + print(" lsys ", addr.lsys\X, "\n"); + print(" lserv ", addr.lserv\X, "\n"); + print(" rsys ", addr.rsys\X, "\n"); + print(" rserv ", addr.rserv\X, "\n"); + print(" laddr ", addr.laddr\X, "\n"); + print(" raddr ", addr.raddr\X, "\n"); +}; + +RFNAMEG = 1; +RFENVG = 2; +RFFDG = 4; +RFNOTEG = 8; +RFPROC = 16; +RFMEM = 32; +RFNOWAIT = 64; +RFCNAMEG = 1024; +RFCENVG = 2048; +RFCFDG = 4096; +RFREND = 8192; +RFNOMNT = 16384; +sizeofQid = 16; +aggr Qid +{ + 'W' 0 path; + 'U' 8 vers; + 'b' 12 type; +}; + +defn +Qid(addr) { + complex Qid addr; + print(" path ", addr.path, "\n"); + print(" vers ", addr.vers, "\n"); + print(" type ", addr.type, "\n"); +}; + +sizeofDir = 60; +aggr Dir +{ + 'u' 0 type; + 'U' 4 dev; + Qid 8 qid; + 'U' 24 mode; + 'U' 28 atime; + 'U' 32 mtime; + 'V' 36 length; + 'X' 44 name; + 'X' 48 uid; + 'X' 52 gid; + 'X' 56 muid; +}; + +defn +Dir(addr) { + complex Dir addr; + print(" type ", addr.type, "\n"); + print(" dev ", addr.dev, "\n"); + print("Qid qid {\n"); + Qid(addr.qid); + print("}\n"); + print(" mode ", addr.mode, "\n"); + print(" atime ", addr.atime, "\n"); + print(" mtime ", addr.mtime, "\n"); + print(" length ", addr.length, "\n"); + print(" name ", addr.name\X, "\n"); + print(" uid ", addr.uid\X, "\n"); + print(" gid ", addr.gid\X, "\n"); + print(" muid ", addr.muid\X, "\n"); +}; + +sizeofWaitmsg = 20; +aggr Waitmsg +{ + 'D' 0 pid; + 'a' 4 time; + 'X' 16 msg; +}; + +defn +Waitmsg(addr) { + complex Waitmsg addr; + print(" pid ", addr.pid, "\n"); + print(" time ", addr.time, "\n"); + print(" msg ", addr.msg\X, "\n"); +}; + +sizeofIOchunk = 8; +aggr IOchunk +{ + 'X' 0 addr; + 'U' 4 len; +}; + +defn +IOchunk(addr) { + complex IOchunk addr; + print(" addr ", addr.addr\X, "\n"); + print(" len ", addr.len, "\n"); +}; + +sizeofPool = 88; +aggr Pool +{ + 'X' 0 name; + 'U' 4 maxsize; + 'U' 8 cursize; + 'U' 12 curfree; + 'U' 16 curalloc; + 'U' 20 minarena; + 'U' 24 quantum; + 'U' 28 minblock; + 'X' 32 freeroot; + 'X' 36 arenalist; + 'X' 40 alloc; + 'X' 44 merge; + 'X' 48 move; + 'D' 52 flags; + 'D' 56 nfree; + 'D' 60 lastcompact; + 'X' 64 lock; + 'X' 68 unlock; + 'X' 72 print; + 'X' 76 panic; + 'X' 80 logstack; + 'X' 84 private; +}; + +defn +Pool(addr) { + complex Pool addr; + print(" name ", addr.name\X, "\n"); + print(" maxsize ", addr.maxsize, "\n"); + print(" cursize ", addr.cursize, "\n"); + print(" curfree ", addr.curfree, "\n"); + print(" curalloc ", addr.curalloc, "\n"); + print(" minarena ", addr.minarena, "\n"); + print(" quantum ", addr.quantum, "\n"); + print(" minblock ", addr.minblock, "\n"); + print(" freeroot ", addr.freeroot\X, "\n"); + print(" arenalist ", addr.arenalist\X, "\n"); + print(" alloc ", addr.alloc\X, "\n"); + print(" merge ", addr.merge\X, "\n"); + print(" move ", addr.move\X, "\n"); + print(" flags ", addr.flags, "\n"); + print(" nfree ", addr.nfree, "\n"); + print(" lastcompact ", addr.lastcompact, "\n"); + print(" lock ", addr.lock\X, "\n"); + print(" unlock ", addr.unlock\X, "\n"); + print(" print ", addr.print\X, "\n"); + print(" panic ", addr.panic\X, "\n"); + print(" logstack ", addr.logstack\X, "\n"); + print(" private ", addr.private\X, "\n"); +}; + +complex Pool mainmem; +complex Pool imagmem; +POOL_ANTAGONISM = 1; +POOL_PARANOIA = 2; +POOL_VERBOSITY = 4; +POOL_DEBUGGING = 8; +POOL_LOGGING = 16; +POOL_TOLERANCE = 32; +POOL_NOREUSE = 64; +sizeofBhdr = 8; +aggr Bhdr +{ + 'U' 0 magic; + 'U' 4 size; +}; + +defn +Bhdr(addr) { + complex Bhdr addr; + print(" magic ", addr.magic, "\n"); + print(" size ", addr.size, "\n"); +}; + +NOT_MAGIC = 3735943697; +DEAD_MAGIC = 3735936685; +TAIL_MAGIC0 = 190; +TAIL_MAGIC1 = 239; +sizeofBtail = 8; +aggr Btail +{ + 'b' 0 magic0; + 'a' 1 datasize; + 'b' 3 magic1; + 'U' 4 size; +}; + +defn +Btail(addr) { + complex Btail addr; + print(" magic0 ", addr.magic0, "\n"); + print(" datasize ", addr.datasize, "\n"); + print(" magic1 ", addr.magic1, "\n"); + print(" size ", addr.size, "\n"); +}; + +sizeofFree = 24; +aggr Free +{ + { + 'U' 0 magic; + 'U' 4 size; + }; + 'A' Free 8 left; + 'A' Free 12 right; + 'A' Free 16 next; + 'A' Free 20 prev; +}; + +defn +Free(addr) { + complex Free addr; + print("Bhdr {\n"); + Bhdr(addr+0); + print("}\n"); + print(" left ", addr.left\X, "\n"); + print(" right ", addr.right\X, "\n"); + print(" next ", addr.next\X, "\n"); + print(" prev ", addr.prev\X, "\n"); +}; + +FREE_MAGIC = 3126770193; +sizeofAlloc = 8; +aggr Alloc +{ + { + 'U' 0 magic; + 'U' 4 size; + }; +}; + +defn +Alloc(addr) { + complex Alloc addr; + print("Bhdr {\n"); + Bhdr(addr+0); + print("}\n"); +}; + +ALLOC_MAGIC = 168889353; +UNALLOC_MAGIC = 3400535327; +sizeofArena = 24; +aggr Arena +{ + { + 'U' 0 magic; + 'U' 4 size; + }; + 'A' Arena 8 aup; + 'A' Arena 12 down; + 'U' 16 asize; + 'U' 20 pad; +}; + +defn +Arena(addr) { + complex Arena addr; + print("Bhdr {\n"); + Bhdr(addr+0); + print("}\n"); + print(" aup ", addr.aup\X, "\n"); + print(" down ", addr.down\X, "\n"); + print(" asize ", addr.asize, "\n"); + print(" pad ", addr.pad, "\n"); +}; + +ARENA_MAGIC = 3231835599; +ARENATAIL_MAGIC = 3965590029; +ALIGN_MAGIC = 2716979649; +MINBLOCKSIZE = 32; +complex Free checklist:t; +complex Free checklist:q; +complex Free checktree:t; +complex Free ltreewalk:t; +complex Free treelookup:t; +complex Free treeinsert:tree; +complex Free treeinsert:node; +complex Free treeinsert:loc; +complex Free treeinsert:repl; +complex Free treedelete:tree; +complex Free treedelete:node; +complex Free treedelete:loc; +complex Free treedelete:lsucc; +complex Free treedelete:succ; +complex Free treelookupgt:t; +complex Free treelookupgt:lastgood; +complex Free listadd:list; +complex Free listadd:node; +complex Free listdelete:list; +complex Free listdelete:node; +complex Pool pooladd:p; +complex Alloc pooladd:anode; +complex Free pooladd:lst; +complex Free pooladd:olst; +complex Free pooladd:node; +complex Free pooladd:parent; +complex Pool pooldel:p; +complex Free pooldel:node; +complex Free pooldel:lst; +complex Free pooldel:olst; +complex Free pooldel:parent; +complex Pool dsize2bsize:p; +complex Pool bsize2asize:p; +complex Pool blockmerge:pool; +complex Bhdr blockmerge:a; +complex Bhdr blockmerge:b; +complex Btail blockmerge:t; +complex Bhdr blocksetsize:b; +complex Btail blocksetsize:t; +complex Alloc getdsize:b; +complex Btail getdsize:t; +complex Pool blocksetdsize:p; +complex Alloc blocksetdsize:b; +complex Btail blocksetdsize:t; +complex Pool trim:p; +complex Alloc trim:b; +complex Alloc trim:frag; +complex Pool freefromfront:p; +complex Alloc freefromfront:b; +complex Alloc freefromfront:bb; +complex Arena arenasetsize:a; +complex Bhdr arenasetsize:atail; +complex Pool poolnewarena:p; +complex Arena poolnewarena:a; +complex Arena poolnewarena:ap; +complex Arena poolnewarena:lastap; +complex Alloc poolnewarena:b; +complex Pool blockgrow:p; +complex Bhdr blockgrow:b; +complex Alloc blockgrow:a; +complex Bhdr blockgrow:bnxt; +complex Alloc blockgrow:a; +complex Pool arenamerge:p; +complex Arena arenamerge:bot; +complex Arena arenamerge:top; +complex Bhdr arenamerge:bbot; +complex Bhdr arenamerge:btop; +complex Btail arenamerge:t; +complex Pool dumpblock:p; +complex Bhdr dumpblock:b; +complex Pool printblock:p; +complex Bhdr printblock:b; +complex Pool panicblock:p; +complex Bhdr panicblock:b; +complex Pool blockcheck:p; +complex Bhdr blockcheck:b; +complex Alloc blockcheck:a; +complex Btail blockcheck:t; +FLOATING_MAGIC = 3419130827; +complex Pool arenacompact:p; +complex Arena arenacompact:a; +complex Bhdr arenacompact:b; +complex Bhdr arenacompact:wb; +complex Bhdr arenacompact:eb; +complex Bhdr arenacompact:nxt; +complex Pool poolcompactl:pool; +complex Arena poolcompactl:a; +complex Pool B2D:p; +complex Alloc B2D:a; +complex Pool D2B:p; +complex Alloc D2B:a; +complex Pool poolallocl:p; +complex Free poolallocl:fb; +complex Alloc poolallocl:ab; +complex Pool poolreallocl:p; +complex Alloc poolreallocl:a; +complex Bhdr poolreallocl:left; +complex Bhdr poolreallocl:right; +complex Bhdr poolreallocl:newb; +complex Btail poolreallocl:t; +complex Pool poolallocalignl:p; +complex Alloc poolallocalignl:b; +complex Pool poolfreel:p; +complex Alloc poolfreel:ab; +complex Bhdr poolfreel:back; +complex Bhdr poolfreel:fwd; +complex Pool poolalloc:p; +complex Pool poolallocalign:p; +complex Pool poolcompact:p; +complex Pool poolrealloc:p; +complex Pool poolfree:p; +complex Pool poolmsize:p; +complex Alloc poolmsize:b; +complex Pool poolcheckarena:p; +complex Arena poolcheckarena:a; +complex Bhdr poolcheckarena:b; +complex Bhdr poolcheckarena:atail; +complex Pool poolcheckl:p; +complex Arena poolcheckl:a; +complex Pool poolcheck:p; +complex Pool poolblockcheck:p; +complex Pool pooldumpl:p; +complex Arena pooldumpl:a; +complex Pool pooldump:p; +complex Pool pooldumparena:p; +complex Arena pooldumparena:a; +complex Bhdr pooldumparena:b; diff --git a/sys/src/libc/port/pool.c b/sys/src/libc/port/pool.c new file mode 100755 index 000000000..915fca3f1 --- /dev/null +++ b/sys/src/libc/port/pool.c @@ -0,0 +1,1466 @@ +/* + * This allocator takes blocks from a coarser allocator (p->alloc) and + * uses them as arenas. + * + * An arena is split into a sequence of blocks of variable size. The + * blocks begin with a Bhdr that denotes the length (including the Bhdr) + * of the block. An arena begins with an Arena header block (Arena, + * ARENA_MAGIC) and ends with a Bhdr block with magic ARENATAIL_MAGIC and + * size 0. Intermediate blocks are either allocated or free. At the end + * of each intermediate block is a Btail, which contains information + * about where the block starts. This is useful for walking backwards. + * + * Free blocks (Free*) have a magic value of FREE_MAGIC in their Bhdr + * headers. They are kept in a binary tree (p->freeroot) traversible by + * walking ->left and ->right. Each node of the binary tree is a pointer + * to a circular doubly-linked list (next, prev) of blocks of identical + * size. Blocks are added to this ``tree of lists'' by pooladd(), and + * removed by pooldel(). + * + * When freed, adjacent blocks are coalesced to create larger blocks when + * possible. + * + * Allocated blocks (Alloc*) have one of two magic values: ALLOC_MAGIC or + * UNALLOC_MAGIC. When blocks are released from the pool, they have + * magic value UNALLOC_MAGIC. Once the block has been trimmed by trim() + * and the amount of user-requested data has been recorded in the + * datasize field of the tail, the magic value is changed to ALLOC_MAGIC. + * All blocks returned to callers should be of type ALLOC_MAGIC, as + * should all blocks passed to us by callers. The amount of data the user + * asked us for can be found by subtracting the short in tail->datasize + * from header->size. Further, the up to at most four bytes between the + * end of the user-requested data block and the actual Btail structure are + * marked with a magic value, which is checked to detect user overflow. + * + * The arenas returned by p->alloc are kept in a doubly-linked list + * (p->arenalist) running through the arena headers, sorted by descending + * base address (prev, next). When a new arena is allocated, we attempt + * to merge it with its two neighbors via p->merge. + */ + +#include <u.h> +#include <libc.h> +#include <pool.h> + +typedef struct Alloc Alloc; +typedef struct Arena Arena; +typedef struct Bhdr Bhdr; +typedef struct Btail Btail; +typedef struct Free Free; + +struct Bhdr { + ulong magic; + ulong size; +}; +enum { + NOT_MAGIC = 0xdeadfa11, + DEAD_MAGIC = 0xdeaddead, +}; +#define B2NB(b) ((Bhdr*)((uchar*)(b)+(b)->size)) + +#define SHORT(x) (((x)[0] << 8) | (x)[1]) +#define PSHORT(p, x) \ + (((uchar*)(p))[0] = ((x)>>8)&0xFF, \ + ((uchar*)(p))[1] = (x)&0xFF) + +enum { + TAIL_MAGIC0 = 0xBE, + TAIL_MAGIC1 = 0xEF +}; +struct Btail { + uchar magic0; + uchar datasize[2]; + uchar magic1; + ulong size; /* same as Bhdr->size */ +}; +#define B2T(b) ((Btail*)((uchar*)(b)+(b)->size-sizeof(Btail))) +#define B2PT(b) ((Btail*)((uchar*)(b)-sizeof(Btail))) +#define T2HDR(t) ((Bhdr*)((uchar*)(t)+sizeof(Btail)-(t)->size)) +struct Free { + Bhdr; + Free* left; + Free* right; + Free* next; + Free* prev; +}; +enum { + FREE_MAGIC = 0xBA5EBA11, +}; + +/* + * the point of the notused fields is to make 8c differentiate + * between Bhdr and Allocblk, and between Kempt and Unkempt. + */ +struct Alloc { + Bhdr; +}; +enum { + ALLOC_MAGIC = 0x0A110C09, + UNALLOC_MAGIC = 0xCAB00D1E+1, +}; + +struct Arena { + Bhdr; + Arena* aup; + Arena* down; + ulong asize; + ulong pad; /* to a multiple of 8 bytes */ +}; +enum { + ARENA_MAGIC = 0xC0A1E5CE+1, + ARENATAIL_MAGIC = 0xEC5E1A0C+1, +}; +#define A2TB(a) ((Bhdr*)((uchar*)(a)+(a)->asize-sizeof(Bhdr))) +#define A2B(a) B2NB(a) + +enum { + ALIGN_MAGIC = 0xA1F1D1C1, +}; + +enum { + MINBLOCKSIZE = sizeof(Free)+sizeof(Btail) +}; + +static uchar datamagic[] = { 0xFE, 0xF1, 0xF0, 0xFA }; + +#define Poison (void*)0xCafeBabe + +#define _B2D(a) ((void*)((uchar*)a+sizeof(Bhdr))) +#define _D2B(v) ((Alloc*)((uchar*)v-sizeof(Bhdr))) + +// static void* _B2D(void*); +// static void* _D2B(void*); +static void* B2D(Pool*, Alloc*); +static Alloc* D2B(Pool*, void*); +static Arena* arenamerge(Pool*, Arena*, Arena*); +static void blockcheck(Pool*, Bhdr*); +static Alloc* blockmerge(Pool*, Bhdr*, Bhdr*); +static Alloc* blocksetdsize(Pool*, Alloc*, ulong); +static Bhdr* blocksetsize(Bhdr*, ulong); +static ulong bsize2asize(Pool*, ulong); +static ulong dsize2bsize(Pool*, ulong); +static ulong getdsize(Alloc*); +static Alloc* trim(Pool*, Alloc*, ulong); +static Free* listadd(Free*, Free*); +static Free* listdelete(Free*, Free*); +static void logstack(Pool*); +static Free** ltreewalk(Free**, ulong); +static void memmark(void*, int, ulong); +static Free* pooladd(Pool*, Alloc*); +static void* poolallocl(Pool*, ulong); +static void poolcheckl(Pool*); +static void poolcheckarena(Pool*, Arena*); +static int poolcompactl(Pool*); +static Alloc* pooldel(Pool*, Free*); +static void pooldumpl(Pool*); +static void pooldumparena(Pool*, Arena*); +static void poolfreel(Pool*, void*); +static void poolnewarena(Pool*, ulong); +static void* poolreallocl(Pool*, void*, ulong); +static Free* treedelete(Free*, Free*); +static Free* treeinsert(Free*, Free*); +static Free* treelookup(Free*, ulong); +static Free* treelookupgt(Free*, ulong); + +/* + * Debugging + * + * Antagonism causes blocks to always be filled with garbage if their + * contents are undefined. This tickles both programs and the library. + * It's a linear time hit but not so noticeable during nondegenerate use. + * It would be worth leaving in except that it negates the benefits of the + * kernel's demand-paging. The tail magic and end-of-data magic + * provide most of the user-visible benefit that antagonism does anyway. + * + * Paranoia causes the library to recheck the entire pool on each lock + * or unlock. A failed check on unlock means we tripped over ourselves, + * while a failed check on lock tends to implicate the user. Paranoia has + * the potential to slow things down a fair amount for pools with large + * numbers of allocated blocks. It completely negates all benefits won + * by the binary tree. Turning on paranoia in the kernel makes it painfully + * slow. + * + * Verbosity induces the dumping of the pool via p->print at each lock operation. + * By default, only one line is logged for each alloc, free, and realloc. + */ + +/* the if(!x);else avoids ``dangling else'' problems */ +#define antagonism if(!(p->flags & POOL_ANTAGONISM)){}else +#define paranoia if(!(p->flags & POOL_PARANOIA)){}else +#define verbosity if(!(p->flags & POOL_VERBOSITY)){}else + +#define DPRINT if(!(p->flags & POOL_DEBUGGING)){}else p->print +#define LOG if(!(p->flags & POOL_LOGGING)){}else p->print + +/* + * Tree walking + */ + +static void +checklist(Free *t) +{ + Free *q; + + for(q=t->next; q!=t; q=q->next){ + assert(q->size == t->size); + assert(q->next==nil || q->next->prev==q); + assert(q->prev==nil || q->prev->next==q); + // assert(q->left==nil); + // assert(q->right==nil); + assert(q->magic==FREE_MAGIC); + } +} + +static void +checktree(Free *t, int a, int b) +{ + assert(t->magic==FREE_MAGIC); + assert(a < t->size && t->size < b); + assert(t->next==nil || t->next->prev==t); + assert(t->prev==nil || t->prev->next==t); + checklist(t); + if(t->left) + checktree(t->left, a, t->size); + if(t->right) + checktree(t->right, t->size, b); + +} + +/* ltreewalk: return address of pointer to node of size == size */ +static Free** +ltreewalk(Free **t, ulong size) +{ + assert(t != nil /* ltreewalk */); + + for(;;) { + if(*t == nil) + return t; + + assert((*t)->magic == FREE_MAGIC); + + if(size == (*t)->size) + return t; + if(size < (*t)->size) + t = &(*t)->left; + else + t = &(*t)->right; + } +} + +/* treelookup: find node in tree with size == size */ +static Free* +treelookup(Free *t, ulong size) +{ + return *ltreewalk(&t, size); +} + +/* treeinsert: insert node into tree */ +static Free* +treeinsert(Free *tree, Free *node) +{ + Free **loc, *repl; + + assert(node != nil /* treeinsert */); + + loc = ltreewalk(&tree, node->size); + if(*loc == nil) { + node->left = nil; + node->right = nil; + } else { /* replace existing node */ + repl = *loc; + node->left = repl->left; + node->right = repl->right; + } + *loc = node; + return tree; +} + +/* treedelete: remove node from tree */ +static Free* +treedelete(Free *tree, Free *node) +{ + Free **loc, **lsucc, *succ; + + assert(node != nil /* treedelete */); + + loc = ltreewalk(&tree, node->size); + assert(*loc == node); + + if(node->left == nil) + *loc = node->right; + else if(node->right == nil) + *loc = node->left; + else { + /* have two children, use inorder successor as replacement */ + for(lsucc = &node->right; (*lsucc)->left; lsucc = &(*lsucc)->left) + ; + succ = *lsucc; + *lsucc = succ->right; + succ->left = node->left; + succ->right = node->right; + *loc = succ; + } + + node->left = node->right = Poison; + return tree; +} + +/* treelookupgt: find smallest node in tree with size >= size */ +static Free* +treelookupgt(Free *t, ulong size) +{ + Free *lastgood; /* last node we saw that was big enough */ + + lastgood = nil; + for(;;) { + if(t == nil) + return lastgood; + if(size == t->size) + return t; + if(size < t->size) { + lastgood = t; + t = t->left; + } else + t = t->right; + } +} + +/* + * List maintenance + */ + +/* listadd: add a node to a doubly linked list */ +static Free* +listadd(Free *list, Free *node) +{ + if(list == nil) { + node->next = node; + node->prev = node; + return node; + } + + node->prev = list->prev; + node->next = list; + + node->prev->next = node; + node->next->prev = node; + + return list; +} + +/* listdelete: remove node from a doubly linked list */ +static Free* +listdelete(Free *list, Free *node) +{ + if(node->next == node) { /* singular list */ + node->prev = node->next = Poison; + return nil; + } + + node->next->prev = node->prev; + node->prev->next = node->next; + + if(list == node) + list = node->next; + + node->prev = node->next = Poison; + return list; +} + +/* + * Pool maintenance + */ + +/* pooladd: add anode to the free pool */ +static Free* +pooladd(Pool *p, Alloc *anode) +{ + Free *lst, *olst; + Free *node; + Free **parent; + + antagonism { + memmark(_B2D(anode), 0xF7, anode->size-sizeof(Bhdr)-sizeof(Btail)); + } + + node = (Free*)anode; + node->magic = FREE_MAGIC; + parent = ltreewalk(&p->freeroot, node->size); + olst = *parent; + lst = listadd(olst, node); + if(olst != lst) /* need to update tree */ + *parent = treeinsert(*parent, lst); + p->curfree += node->size; + return node; +} + +/* pooldel: remove node from the free pool */ +static Alloc* +pooldel(Pool *p, Free *node) +{ + Free *lst, *olst; + Free **parent; + + parent = ltreewalk(&p->freeroot, node->size); + olst = *parent; + assert(olst != nil /* pooldel */); + + lst = listdelete(olst, node); + if(lst == nil) + *parent = treedelete(*parent, olst); + else if(lst != olst) + *parent = treeinsert(*parent, lst); + + node->left = node->right = Poison; + p->curfree -= node->size; + + antagonism { + memmark(_B2D(node), 0xF9, node->size-sizeof(Bhdr)-sizeof(Btail)); + } + + node->magic = UNALLOC_MAGIC; + return (Alloc*)node; +} + +/* + * Block maintenance + */ +/* block allocation */ +static ulong +dsize2bsize(Pool *p, ulong sz) +{ + sz += sizeof(Bhdr)+sizeof(Btail); + if(sz < p->minblock) + sz = p->minblock; + if(sz < MINBLOCKSIZE) + sz = MINBLOCKSIZE; + sz = (sz+p->quantum-1)&~(p->quantum-1); + return sz; +} + +static ulong +bsize2asize(Pool *p, ulong sz) +{ + sz += sizeof(Arena)+sizeof(Btail); + if(sz < p->minarena) + sz = p->minarena; + sz = (sz+p->quantum)&~(p->quantum-1); + return sz; +} + +/* blockmerge: merge a and b, known to be adjacent */ +/* both are removed from pool if necessary. */ +static Alloc* +blockmerge(Pool *pool, Bhdr *a, Bhdr *b) +{ + Btail *t; + + assert(B2NB(a) == b); + + if(a->magic == FREE_MAGIC) + pooldel(pool, (Free*)a); + if(b->magic == FREE_MAGIC) + pooldel(pool, (Free*)b); + + t = B2T(a); + t->size = (ulong)Poison; + t->magic0 = NOT_MAGIC; + t->magic1 = NOT_MAGIC; + PSHORT(t->datasize, NOT_MAGIC); + + a->size += b->size; + t = B2T(a); + t->size = a->size; + PSHORT(t->datasize, 0xFFFF); + + b->size = NOT_MAGIC; + b->magic = NOT_MAGIC; + + a->magic = UNALLOC_MAGIC; + return (Alloc*)a; +} + +/* blocksetsize: set the total size of a block, fixing tail pointers */ +static Bhdr* +blocksetsize(Bhdr *b, ulong bsize) +{ + Btail *t; + + assert(b->magic != FREE_MAGIC /* blocksetsize */); + + b->size = bsize; + t = B2T(b); + t->size = b->size; + t->magic0 = TAIL_MAGIC0; + t->magic1 = TAIL_MAGIC1; + return b; +} + +/* getdsize: return the requested data size for an allocated block */ +static ulong +getdsize(Alloc *b) +{ + Btail *t; + t = B2T(b); + return b->size - SHORT(t->datasize); +} + +/* blocksetdsize: set the user data size of a block */ +static Alloc* +blocksetdsize(Pool *p, Alloc *b, ulong dsize) +{ + Btail *t; + uchar *q, *eq; + + assert(b->size >= dsize2bsize(p, dsize)); + assert(b->size - dsize < 0x10000); + + t = B2T(b); + PSHORT(t->datasize, b->size - dsize); + + q=(uchar*)_B2D(b)+dsize; + eq = (uchar*)t; + if(eq > q+4) + eq = q+4; + for(; q<eq; q++) + *q = datamagic[((ulong)(uintptr)q)%nelem(datamagic)]; + + return b; +} + +/* trim: trim a block down to what is needed to hold dsize bytes of user data */ +static Alloc* +trim(Pool *p, Alloc *b, ulong dsize) +{ + ulong extra, bsize; + Alloc *frag; + + bsize = dsize2bsize(p, dsize); + extra = b->size - bsize; + if(b->size - dsize >= 0x10000 || + (extra >= bsize>>2 && extra >= MINBLOCKSIZE && extra >= p->minblock)) { + blocksetsize(b, bsize); + frag = (Alloc*) B2NB(b); + + antagonism { + memmark(frag, 0xF1, extra); + } + + frag->magic = UNALLOC_MAGIC; + blocksetsize(frag, extra); + pooladd(p, frag); + } + + b->magic = ALLOC_MAGIC; + blocksetdsize(p, b, dsize); + return b; +} + +static Alloc* +freefromfront(Pool *p, Alloc *b, ulong skip) +{ + Alloc *bb; + + skip = skip&~(p->quantum-1); + if(skip >= 0x1000 || (skip >= b->size>>2 && skip >= MINBLOCKSIZE && skip >= p->minblock)){ + bb = (Alloc*)((uchar*)b+skip); + blocksetsize(bb, b->size-skip); + bb->magic = UNALLOC_MAGIC; + blocksetsize(b, skip); + b->magic = UNALLOC_MAGIC; + pooladd(p, b); + return bb; + } + return b; +} + +/* + * Arena maintenance + */ + +/* arenasetsize: set arena size, updating tail */ +static void +arenasetsize(Arena *a, ulong asize) +{ + Bhdr *atail; + + a->asize = asize; + atail = A2TB(a); + atail->magic = ARENATAIL_MAGIC; + atail->size = 0; +} + +/* poolnewarena: allocate new arena */ +static void +poolnewarena(Pool *p, ulong asize) +{ + Arena *a; + Arena *ap, *lastap; + Alloc *b; + + LOG(p, "newarena %lud\n", asize); + if(p->cursize+asize > p->maxsize) { + if(poolcompactl(p) == 0){ + LOG(p, "pool too big: %lud+%lud > %lud\n", + p->cursize, asize, p->maxsize); + werrstr("memory pool too large"); + } + return; + } + + if((a = p->alloc(asize)) == nil) { + /* assume errstr set by p->alloc */ + return; + } + + p->cursize += asize; + + /* arena hdr */ + a->magic = ARENA_MAGIC; + blocksetsize(a, sizeof(Arena)); + arenasetsize(a, asize); + blockcheck(p, a); + + /* create one large block in arena */ + b = (Alloc*)A2B(a); + b->magic = UNALLOC_MAGIC; + blocksetsize(b, (uchar*)A2TB(a)-(uchar*)b); + blockcheck(p, b); + pooladd(p, b); + blockcheck(p, b); + + /* sort arena into descending sorted arena list */ + for(lastap=nil, ap=p->arenalist; ap > a; lastap=ap, ap=ap->down) + ; + + if(a->down = ap) /* assign = */ + a->down->aup = a; + + if(a->aup = lastap) /* assign = */ + a->aup->down = a; + else + p->arenalist = a; + + /* merge with surrounding arenas if possible */ + /* must do a with up before down with a (think about it) */ + if(a->aup) + arenamerge(p, a, a->aup); + if(a->down) + arenamerge(p, a->down, a); +} + +/* blockresize: grow a block to encompass space past its end, possibly by */ +/* trimming it into two different blocks. */ +static void +blockgrow(Pool *p, Bhdr *b, ulong nsize) +{ + if(b->magic == FREE_MAGIC) { + Alloc *a; + Bhdr *bnxt; + a = pooldel(p, (Free*)b); + blockcheck(p, a); + blocksetsize(a, nsize); + blockcheck(p, a); + bnxt = B2NB(a); + if(bnxt->magic == FREE_MAGIC) + a = blockmerge(p, a, bnxt); + blockcheck(p, a); + pooladd(p, a); + } else { + Alloc *a; + ulong dsize; + + a = (Alloc*)b; + dsize = getdsize(a); + blocksetsize(a, nsize); + trim(p, a, dsize); + } +} + +/* arenamerge: attempt to coalesce to arenas that might be adjacent */ +static Arena* +arenamerge(Pool *p, Arena *bot, Arena *top) +{ + Bhdr *bbot, *btop; + Btail *t; + + blockcheck(p, bot); + blockcheck(p, top); + assert(bot->aup == top && top > bot); + + if(p->merge == nil || p->merge(bot, top) == 0) + return nil; + + /* remove top from list */ + if(bot->aup = top->aup) /* assign = */ + bot->aup->down = bot; + else + p->arenalist = bot; + + /* save ptrs to last block in bot, first block in top */ + t = B2PT(A2TB(bot)); + bbot = T2HDR(t); + btop = A2B(top); + blockcheck(p, bbot); + blockcheck(p, btop); + + /* grow bottom arena to encompass top */ + arenasetsize(bot, top->asize + ((uchar*)top - (uchar*)bot)); + + /* grow bottom block to encompass space between arenas */ + blockgrow(p, bbot, (uchar*)btop-(uchar*)bbot); + blockcheck(p, bbot); + return bot; +} + +/* dumpblock: print block's vital stats */ +static void +dumpblock(Pool *p, Bhdr *b) +{ + ulong *dp; + ulong dsize; + uchar *cp; + + dp = (ulong*)b; + p->print(p, "pool %s block %p\nhdr %.8lux %.8lux %.8lux %.8lux %.8lux %.8lux\n", + p->name, b, dp[0], dp[1], dp[2], dp[3], dp[4], dp[5], dp[6]); + + dp = (ulong*)B2T(b); + p->print(p, "tail %.8lux %.8lux %.8lux %.8lux %.8lux %.8lux | %.8lux %.8lux\n", + dp[-6], dp[-5], dp[-4], dp[-3], dp[-2], dp[-1], dp[0], dp[1]); + + if(b->magic == ALLOC_MAGIC){ + dsize = getdsize((Alloc*)b); + if(dsize >= b->size) /* user data size corrupt */ + return; + + cp = (uchar*)_B2D(b)+dsize; + p->print(p, "user data "); + p->print(p, "%.2ux %.2ux %.2ux %.2ux %.2ux %.2ux %.2ux %.2ux", + cp[-8], cp[-7], cp[-6], cp[-5], cp[-4], cp[-3], cp[-2], cp[-1]); + p->print(p, " | %.2ux %.2ux %.2ux %.2ux %.2ux %.2ux %.2ux %.2ux\n", + cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]); + } +} + +static void +printblock(Pool *p, Bhdr *b, char *msg) +{ + p->print(p, "%s\n", msg); + dumpblock(p, b); +} + +static void +panicblock(Pool *p, Bhdr *b, char *msg) +{ + p->print(p, "%s\n", msg); + dumpblock(p, b); + p->panic(p, "pool panic"); +} + +/* blockcheck: ensure a block consistent with our expectations */ +/* should only be called when holding pool lock */ +static void +blockcheck(Pool *p, Bhdr *b) +{ + Alloc *a; + Btail *t; + int i, n; + uchar *q, *bq, *eq; + ulong dsize; + + switch(b->magic) { + default: + panicblock(p, b, "bad magic"); + case FREE_MAGIC: + case UNALLOC_MAGIC: + t = B2T(b); + if(t->magic0 != TAIL_MAGIC0 || t->magic1 != TAIL_MAGIC1) + panicblock(p, b, "corrupt tail magic"); + if(T2HDR(t) != b) + panicblock(p, b, "corrupt tail ptr"); + break; + case DEAD_MAGIC: + t = B2T(b); + if(t->magic0 != TAIL_MAGIC0 || t->magic1 != TAIL_MAGIC1) + panicblock(p, b, "corrupt tail magic"); + if(T2HDR(t) != b) + panicblock(p, b, "corrupt tail ptr"); + n = getdsize((Alloc*)b); + q = _B2D(b); + q += 8; + for(i=8; i<n; i++) + if(*q++ != 0xDA) + panicblock(p, b, "dangling pointer write"); + break; + case ARENA_MAGIC: + b = A2TB((Arena*)b); + if(b->magic != ARENATAIL_MAGIC) + panicblock(p, b, "bad arena size"); + /* fall through */ + case ARENATAIL_MAGIC: + if(b->size != 0) + panicblock(p, b, "bad arena tail size"); + break; + case ALLOC_MAGIC: + a = (Alloc*)b; + t = B2T(b); + dsize = getdsize(a); + bq = (uchar*)_B2D(a)+dsize; + eq = (uchar*)t; + + if(t->magic0 != TAIL_MAGIC0){ + /* if someone wrote exactly one byte over and it was a NUL, we sometimes only complain. */ + if((p->flags & POOL_TOLERANCE) && bq == eq && t->magic0 == 0) + printblock(p, b, "mem user overflow (magic0)"); + else + panicblock(p, b, "corrupt tail magic0"); + } + + if(t->magic1 != TAIL_MAGIC1) + panicblock(p, b, "corrupt tail magic1"); + if(T2HDR(t) != b) + panicblock(p, b, "corrupt tail ptr"); + + if(dsize2bsize(p, dsize) > a->size) + panicblock(p, b, "too much block data"); + + if(eq > bq+4) + eq = bq+4; + for(q=bq; q<eq; q++){ + if(*q != datamagic[((uintptr)q)%nelem(datamagic)]){ + if(q == bq && *q == 0 && (p->flags & POOL_TOLERANCE)){ + printblock(p, b, "mem user overflow"); + continue; + } + panicblock(p, b, "mem user overflow"); + } + } + break; + } +} + +/* + * compact an arena by shifting all the free blocks to the end. + * assumes pool lock is held. + */ +enum { + FLOATING_MAGIC = 0xCBCBCBCB, /* temporarily neither allocated nor in the free tree */ +}; + +static int +arenacompact(Pool *p, Arena *a) +{ + Bhdr *b, *wb, *eb, *nxt; + int compacted; + + if(p->move == nil) + p->panic(p, "don't call me when pool->move is nil\n"); + + poolcheckarena(p, a); + eb = A2TB(a); + compacted = 0; + for(b=wb=A2B(a); b && b < eb; b=nxt) { + nxt = B2NB(b); + switch(b->magic) { + case FREE_MAGIC: + pooldel(p, (Free*)b); + b->magic = FLOATING_MAGIC; + break; + case ALLOC_MAGIC: + if(wb != b) { + memmove(wb, b, b->size); + p->move(_B2D(b), _B2D(wb)); + compacted = 1; + } + wb = B2NB(wb); + break; + } + } + + /* + * the only free data is now at the end of the arena, pointed + * at by wb. all we need to do is set its size and get out. + */ + if(wb < eb) { + wb->magic = UNALLOC_MAGIC; + blocksetsize(wb, (uchar*)eb-(uchar*)wb); + pooladd(p, (Alloc*)wb); + } + + return compacted; +} + +/* + * compact a pool by compacting each individual arena. + * 'twould be nice to shift blocks from one arena to the + * next but it's a pain to code. + */ +static int +poolcompactl(Pool *pool) +{ + Arena *a; + int compacted; + + if(pool->move == nil || pool->lastcompact == pool->nfree) + return 0; + + pool->lastcompact = pool->nfree; + compacted = 0; + for(a=pool->arenalist; a; a=a->down) + compacted |= arenacompact(pool, a); + return compacted; +} + +/* +static int +poolcompactl(Pool*) +{ + return 0; +} +*/ + +/* + * Actual allocators + */ + +/* +static void* +_B2D(void *a) +{ + return (uchar*)a+sizeof(Bhdr); +} +*/ + +static void* +B2D(Pool *p, Alloc *a) +{ + if(a->magic != ALLOC_MAGIC) + p->panic(p, "B2D called on unworthy block"); + return _B2D(a); +} + +/* +static void* +_D2B(void *v) +{ + Alloc *a; + a = (Alloc*)((uchar*)v-sizeof(Bhdr)); + return a; +} +*/ + +static Alloc* +D2B(Pool *p, void *v) +{ + Alloc *a; + ulong *u; + + if((uintptr)v&(sizeof(ulong)-1)) + v = (char*)v - ((uintptr)v&(sizeof(ulong)-1)); + u = v; + while(u[-1] == ALIGN_MAGIC) + u--; + a = _D2B(u); + if(a->magic != ALLOC_MAGIC) + p->panic(p, "D2B called on non-block %p (double-free?)", v); + return a; +} + +/* poolallocl: attempt to allocate block to hold dsize user bytes; assumes lock held */ +static void* +poolallocl(Pool *p, ulong dsize) +{ + ulong bsize; + Free *fb; + Alloc *ab; + + if(dsize >= 0x80000000UL){ /* for sanity, overflow */ + werrstr("invalid allocation size"); + return nil; + } + + bsize = dsize2bsize(p, dsize); + + fb = treelookupgt(p->freeroot, bsize); + if(fb == nil) { + poolnewarena(p, bsize2asize(p, bsize)); + if((fb = treelookupgt(p->freeroot, bsize)) == nil) { + /* assume poolnewarena failed and set %r */ + return nil; + } + } + + ab = trim(p, pooldel(p, fb), dsize); + p->curalloc += ab->size; + antagonism { + memset(B2D(p, ab), 0xDF, dsize); + } + return B2D(p, ab); +} + +/* poolreallocl: attempt to grow v to ndsize bytes; assumes lock held */ +static void* +poolreallocl(Pool *p, void *v, ulong ndsize) +{ + Alloc *a; + Bhdr *left, *right, *newb; + Btail *t; + ulong nbsize; + ulong odsize; + ulong obsize; + void *nv; + + if(v == nil) /* for ANSI */ + return poolallocl(p, ndsize); + if(ndsize == 0) { + poolfreel(p, v); + return nil; + } + a = D2B(p, v); + blockcheck(p, a); + odsize = getdsize(a); + obsize = a->size; + + /* can reuse the same block? */ + nbsize = dsize2bsize(p, ndsize); + if(nbsize <= a->size) { + Returnblock: + if(v != _B2D(a)) + memmove(_B2D(a), v, odsize); + a = trim(p, a, ndsize); + p->curalloc -= obsize; + p->curalloc += a->size; + v = B2D(p, a); + return v; + } + + /* can merge with surrounding blocks? */ + right = B2NB(a); + if(right->magic == FREE_MAGIC && a->size+right->size >= nbsize) { + a = blockmerge(p, a, right); + goto Returnblock; + } + + t = B2PT(a); + left = T2HDR(t); + if(left->magic == FREE_MAGIC && left->size+a->size >= nbsize) { + a = blockmerge(p, left, a); + goto Returnblock; + } + + if(left->magic == FREE_MAGIC && right->magic == FREE_MAGIC + && left->size+a->size+right->size >= nbsize) { + a = blockmerge(p, blockmerge(p, left, a), right); + goto Returnblock; + } + + if((nv = poolallocl(p, ndsize)) == nil) + return nil; + + /* maybe the new block is next to us; if so, merge */ + left = T2HDR(B2PT(a)); + right = B2NB(a); + newb = D2B(p, nv); + if(left == newb || right == newb) { + if(left == newb || left->magic == FREE_MAGIC) + a = blockmerge(p, left, a); + if(right == newb || right->magic == FREE_MAGIC) + a = blockmerge(p, a, right); + assert(a->size >= nbsize); + goto Returnblock; + } + + /* enough cleverness */ + memmove(nv, v, odsize); + antagonism { + memset((char*)nv+odsize, 0xDE, ndsize-odsize); + } + poolfreel(p, v); + return nv; +} + +static void* +alignptr(void *v, ulong align, long offset) +{ + char *c; + ulong off; + + c = v; + if(align){ + off = (uintptr)c%align; + if(off != offset){ + c += offset - off; + if(off > offset) + c += align; + } + } + return c; +} + +/* poolspanallocl: allocate as described below; assumes pool locked */ +static void* +poolallocalignl(Pool *p, ulong dsize, ulong align, long offset, ulong span) +{ + ulong asize; + void *v; + char *c; + ulong *u; + int skip; + Alloc *b; + + /* + * allocate block + * dsize bytes + * addr == offset (modulo align) + * does not cross span-byte block boundary + * + * to satisfy alignment, just allocate an extra + * align bytes and then shift appropriately. + * + * to satisfy span, try once and see if we're + * lucky. the second time, allocate 2x asize + * so that we definitely get one not crossing + * the boundary. + */ + if(align){ + if(offset < 0) + offset = align - ((-offset)%align); + else + offset %= align; + } + asize = dsize+align; + v = poolallocl(p, asize); + if(v == nil) + return nil; + if(span && (uintptr)v/span != ((uintptr)v+asize)/span){ + /* try again */ + poolfreel(p, v); + v = poolallocl(p, 2*asize); + if(v == nil) + return nil; + } + + /* + * figure out what pointer we want to return + */ + c = alignptr(v, align, offset); + if(span && (uintptr)c/span != (uintptr)(c+dsize-1)/span){ + c += span - (uintptr)c%span; + c = alignptr(c, align, offset); + if((uintptr)c/span != (uintptr)(c+dsize-1)/span){ + poolfreel(p, v); + werrstr("cannot satisfy dsize %lud span %lud with align %lud+%ld", dsize, span, align, offset); + return nil; + } + } + skip = c - (char*)v; + + /* + * free up the skip bytes before that pointer + * or mark it as unavailable. + */ + b = _D2B(v); + b = freefromfront(p, b, skip); + v = _B2D(b); + skip = c - (char*)v; + if(c > (char*)v){ + u = v; + while(c >= (char*)u+sizeof(ulong)) + *u++ = ALIGN_MAGIC; + } + trim(p, b, skip+dsize); + assert(D2B(p, c) == b); + antagonism { + memset(c, 0xDD, dsize); + } + return c; +} + +/* poolfree: free block obtained from poolalloc; assumes lock held */ +static void +poolfreel(Pool *p, void *v) +{ + Alloc *ab; + Bhdr *back, *fwd; + + if(v == nil) /* for ANSI */ + return; + + ab = D2B(p, v); + blockcheck(p, ab); + + if(p->flags&POOL_NOREUSE){ + int n; + + ab->magic = DEAD_MAGIC; + n = getdsize(ab)-8; + if(n > 0) + memset((uchar*)v+8, 0xDA, n); + return; + } + + p->nfree++; + p->curalloc -= ab->size; + back = T2HDR(B2PT(ab)); + if(back->magic == FREE_MAGIC) + ab = blockmerge(p, back, ab); + + fwd = B2NB(ab); + if(fwd->magic == FREE_MAGIC) + ab = blockmerge(p, ab, fwd); + + pooladd(p, ab); +} + +void* +poolalloc(Pool *p, ulong n) +{ + void *v; + + p->lock(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + v = poolallocl(p, n); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p); + LOG(p, "poolalloc %p %lud = %p\n", p, n, v); + p->unlock(p); + return v; +} + +void* +poolallocalign(Pool *p, ulong n, ulong align, long offset, ulong span) +{ + void *v; + + p->lock(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + v = poolallocalignl(p, n, align, offset, span); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p); + LOG(p, "poolalignspanalloc %p %lud %lud %lud %ld = %p\n", p, n, align, span, offset, v); + p->unlock(p); + return v; +} + +int +poolcompact(Pool *p) +{ + int rv; + + p->lock(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + rv = poolcompactl(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + LOG(p, "poolcompact %p\n", p); + p->unlock(p); + return rv; +} + +void* +poolrealloc(Pool *p, void *v, ulong n) +{ + void *nv; + + p->lock(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + nv = poolreallocl(p, v, n); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p); + LOG(p, "poolrealloc %p %p %ld = %p\n", p, v, n, nv); + p->unlock(p); + return nv; +} + +void +poolfree(Pool *p, void *v) +{ + p->lock(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + poolfreel(p, v); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p); + LOG(p, "poolfree %p %p\n", p, v); + p->unlock(p); +} + +/* + * Return the real size of a block, and let the user use it. + */ +ulong +poolmsize(Pool *p, void *v) +{ + Alloc *b; + ulong dsize; + + p->lock(p); + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + if(v == nil) /* consistency with other braindead ANSI-ness */ + dsize = 0; + else { + b = D2B(p, v); + dsize = (b->size&~(p->quantum-1)) - sizeof(Bhdr) - sizeof(Btail); + assert(dsize >= getdsize(b)); + blocksetdsize(p, b, dsize); + } + paranoia { + poolcheckl(p); + } + verbosity { + pooldumpl(p); + } + if(p->logstack && (p->flags & POOL_LOGGING)) p->logstack(p); + LOG(p, "poolmsize %p %p = %ld\n", p, v, dsize); + p->unlock(p); + return dsize; +} + +/* + * Debugging + */ + +static void +poolcheckarena(Pool *p, Arena *a) +{ + Bhdr *b; + Bhdr *atail; + + atail = A2TB(a); + for(b=a; b->magic != ARENATAIL_MAGIC && b<atail; b=B2NB(b)) + blockcheck(p, b); + blockcheck(p, b); + if(b != atail) + p->panic(p, "found wrong tail"); +} + +static void +poolcheckl(Pool *p) +{ + Arena *a; + + for(a=p->arenalist; a; a=a->down) + poolcheckarena(p, a); + if(p->freeroot) + checktree(p->freeroot, 0, 1<<30); +} + +void +poolcheck(Pool *p) +{ + p->lock(p); + poolcheckl(p); + p->unlock(p); +} + +void +poolblockcheck(Pool *p, void *v) +{ + if(v == nil) + return; + + p->lock(p); + blockcheck(p, D2B(p, v)); + p->unlock(p); +} + +static void +pooldumpl(Pool *p) +{ + Arena *a; + + p->print(p, "pool %p %s\n", p, p->name); + for(a=p->arenalist; a; a=a->down) + pooldumparena(p, a); +} + +void +pooldump(Pool *p) +{ + p->lock(p); + pooldumpl(p); + p->unlock(p); +} + +static void +pooldumparena(Pool *p, Arena *a) +{ + Bhdr *b; + + for(b=a; b->magic != ARENATAIL_MAGIC; b=B2NB(b)) + p->print(p, "(%p %.8lux %lud)", b, b->magic, b->size); + p->print(p, "\n"); +} + +/* + * mark the memory in such a way that we know who marked it + * (via the signature) and we know where the marking started. + */ +static void +memmark(void *v, int sig, ulong size) +{ + uchar *p, *ep; + ulong *lp, *elp; + lp = v; + elp = lp+size/4; + while(lp < elp) + *lp++ = (sig<<24) ^ ((uintptr)lp-(uintptr)v); + p = (uchar*)lp; + ep = (uchar*)v+size; + while(p<ep) + *p++ = sig; +} diff --git a/sys/src/libc/port/pow.c b/sys/src/libc/port/pow.c new file mode 100755 index 000000000..0a5a0b5cd --- /dev/null +++ b/sys/src/libc/port/pow.c @@ -0,0 +1,69 @@ +#include <u.h> +#include <libc.h> + +double +pow(double x, double y) /* return x ^ y (exponentiation) */ +{ + double xy, y1, ye; + long i; + int ex, ey, flip; + + if(y == 0.0) + return 1.0; + + flip = 0; + if(y < 0.){ + y = -y; + flip = 1; + } + y1 = modf(y, &ye); + if(y1 != 0.0){ + if(x <= 0.) + goto zreturn; + if(y1 > 0.5) { + y1 -= 1.; + ye += 1.; + } + xy = exp(y1 * log(x)); + }else + xy = 1.0; + if(ye > 0x7FFFFFFF){ /* should be ~0UL but compiler can't convert double to ulong */ + if(x <= 0.){ + zreturn: + if(x==0. && !flip) + return 0.; + return NaN(); + } + if(flip){ + if(y == .5) + return 1./sqrt(x); + y = -y; + }else if(y == .5) + return sqrt(x); + return exp(y * log(x)); + } + x = frexp(x, &ex); + ey = 0; + i = ye; + if(i) + for(;;){ + if(i & 1){ + xy *= x; + ey += ex; + } + i >>= 1; + if(i == 0) + break; + x *= x; + ex <<= 1; + if(x < .5){ + x += x; + ex -= 1; + } + } + if(flip){ + xy = 1. / xy; + ey = -ey; + } + return ldexp(xy, ey); +} diff --git a/sys/src/libc/port/pow10.c b/sys/src/libc/port/pow10.c new file mode 100755 index 000000000..7e09f3cc4 --- /dev/null +++ b/sys/src/libc/port/pow10.c @@ -0,0 +1,49 @@ +#include <u.h> +#include <libc.h> + +/* + * this table might overflow 127-bit exponent representations. + * in that case, truncate it after 1.0e38. + * it is important to get all one can from this + * routine since it is used in atof to scale numbers. + * the presumption is that C converts fp numbers better + * than multipication of lower powers of 10. + */ +static +double tab[] = +{ + 1.0e0, 1.0e1, 1.0e2, 1.0e3, 1.0e4, 1.0e5, 1.0e6, 1.0e7, 1.0e8, 1.0e9, + 1.0e10, 1.0e11, 1.0e12, 1.0e13, 1.0e14, 1.0e15, 1.0e16, 1.0e17, 1.0e18, 1.0e19, + 1.0e20, 1.0e21, 1.0e22, 1.0e23, 1.0e24, 1.0e25, 1.0e26, 1.0e27, 1.0e28, 1.0e29, + 1.0e30, 1.0e31, 1.0e32, 1.0e33, 1.0e34, 1.0e35, 1.0e36, 1.0e37, 1.0e38, 1.0e39, + 1.0e40, 1.0e41, 1.0e42, 1.0e43, 1.0e44, 1.0e45, 1.0e46, 1.0e47, 1.0e48, 1.0e49, + 1.0e50, 1.0e51, 1.0e52, 1.0e53, 1.0e54, 1.0e55, 1.0e56, 1.0e57, 1.0e58, 1.0e59, + 1.0e60, 1.0e61, 1.0e62, 1.0e63, 1.0e64, 1.0e65, 1.0e66, 1.0e67, 1.0e68, 1.0e69, + 1.0e70, 1.0e71, 1.0e72, 1.0e73, 1.0e74, 1.0e75, 1.0e76, 1.0e77, 1.0e78, 1.0e79, + 1.0e80, 1.0e81, 1.0e82, 1.0e83, 1.0e84, 1.0e85, 1.0e86, 1.0e87, 1.0e88, 1.0e89, + 1.0e90, 1.0e91, 1.0e92, 1.0e93, 1.0e94, 1.0e95, 1.0e96, 1.0e97, 1.0e98, 1.0e99, + 1.0e100,1.0e101,1.0e102,1.0e103,1.0e104,1.0e105,1.0e106,1.0e107,1.0e108,1.0e109, + 1.0e110,1.0e111,1.0e112,1.0e113,1.0e114,1.0e115,1.0e116,1.0e117,1.0e118,1.0e119, + 1.0e120,1.0e121,1.0e122,1.0e123,1.0e124,1.0e125,1.0e126,1.0e127,1.0e128,1.0e129, + 1.0e130,1.0e131,1.0e132,1.0e133,1.0e134,1.0e135,1.0e136,1.0e137,1.0e138,1.0e139, + 1.0e140,1.0e141,1.0e142,1.0e143,1.0e144,1.0e145,1.0e146,1.0e147,1.0e148,1.0e149, + 1.0e150,1.0e151,1.0e152,1.0e153,1.0e154,1.0e155,1.0e156,1.0e157,1.0e158,1.0e159, +}; + +double +pow10(int n) +{ + int m; + + if(n < 0) { + n = -n; + if(n < sizeof(tab)/sizeof(tab[0])) + return 1/tab[n]; + m = n/2; + return 1/(pow10(m) * pow10(n-m)); + } + if(n < sizeof(tab)/sizeof(tab[0])) + return tab[n]; + m = n/2; + return pow10(m) * pow10(n-m); +} diff --git a/sys/src/libc/port/profile.c b/sys/src/libc/port/profile.c new file mode 100755 index 000000000..5647e3bf1 --- /dev/null +++ b/sys/src/libc/port/profile.c @@ -0,0 +1,280 @@ +#include <u.h> +#include <libc.h> +#include <tos.h> + +extern long _callpc(void**); +extern long _savearg(void); + +static ulong khz; +static ulong perr; +static int havecycles; + +typedef struct Plink Plink; +struct Plink +{ + Plink *old; + Plink *down; + Plink *link; + long pc; + long count; + vlong time; +}; + +#pragma profile off + +ulong +_profin(void) +{ + void *dummy; + long pc; + Plink *pp, *p; + ulong arg; + vlong t; + + arg = _savearg(); + pc = _callpc(&dummy); + pp = _tos->prof.pp; + if(pp == 0 || (_tos->prof.pid && _tos->pid != _tos->prof.pid)) + return arg; + + for(p=pp->down; p; p=p->link) + if(p->pc == pc) + goto out; + p = _tos->prof.next + 1; + if(p >= _tos->prof.last) { + _tos->prof.pp = 0; + perr++; + return arg; + } + _tos->prof.next = p; + p->link = pp->down; + pp->down = p; + p->pc = pc; + p->old = pp; + p->down = 0; + p->count = 0; + p->time = 0LL; + +out: + _tos->prof.pp = p; + p->count++; + switch(_tos->prof.what){ + case Profkernel: + p->time = p->time - _tos->pcycles; + goto proftime; + case Profuser: + /* Add kernel cycles on proc entry */ + p->time = p->time + _tos->kcycles; + /* fall through */ + case Proftime: + proftime: /* Subtract cycle counter on proc entry */ + cycles((uvlong*)&t); + p->time = p->time - t; + break; + case Profsample: + p->time = p->time - _tos->clock; + break; + } + return arg; /* disgusting linkage */ +} + +ulong +_profout(void) +{ + Plink *p; + ulong arg; + vlong t; + + arg = _savearg(); + p = _tos->prof.pp; + if (p == nil || (_tos->prof.pid != 0 && _tos->pid != _tos->prof.pid)) + return arg; /* Not our process */ + switch(_tos->prof.what){ + case Profkernel: /* Add proc cycles on proc entry */ + p->time = p->time + _tos->pcycles; + goto proftime; + case Profuser: /* Subtract kernel cycles on proc entry */ + p->time = p->time - _tos->kcycles; + /* fall through */ + case Proftime: + proftime: /* Add cycle counter on proc entry */ + cycles((uvlong*)&t); + p->time = p->time + t; + break; + case Profsample: + p->time = p->time + _tos->clock; + break; + } + _tos->prof.pp = p->old; + return arg; +} + +void +_profdump(void) +{ + int f; + long n; + Plink *p; + char *vp; + char filename[64]; + + if (_tos->prof.what == 0) + return; /* No profiling */ + if (_tos->prof.pid != 0 && _tos->pid != _tos->prof.pid) + return; /* Not our process */ + if(perr) + fprint(2, "%lud Prof errors\n", perr); + _tos->prof.pp = nil; + if (_tos->prof.pid) + snprint(filename, sizeof filename - 1, "prof.%ld", _tos->prof.pid); + else + snprint(filename, sizeof filename - 1, "prof.out"); + f = create(filename, 1, 0666); + if(f < 0) { + perror("create prof.out"); + return; + } + _tos->prof.pid = ~0; /* make sure data gets dumped once */ + switch(_tos->prof.what){ + case Profkernel: + cycles((uvlong*)&_tos->prof.first->time); + _tos->prof.first->time = _tos->prof.first->time + _tos->pcycles; + break; + case Profuser: + cycles((uvlong*)&_tos->prof.first->time); + _tos->prof.first->time = _tos->prof.first->time - _tos->kcycles; + break; + case Proftime: + cycles((uvlong*)&_tos->prof.first->time); + break; + case Profsample: + _tos->prof.first->time = _tos->clock; + break; + } + vp = (char*)_tos->prof.first; + + for(p = _tos->prof.first; p <= _tos->prof.next; p++) { + + /* + * short down + */ + n = 0xffff; + if(p->down) + n = p->down - _tos->prof.first; + vp[0] = n>>8; + vp[1] = n; + + /* + * short right + */ + n = 0xffff; + if(p->link) + n = p->link - _tos->prof.first; + vp[2] = n>>8; + vp[3] = n; + vp += 4; + + /* + * long pc + */ + n = p->pc; + vp[0] = n>>24; + vp[1] = n>>16; + vp[2] = n>>8; + vp[3] = n; + vp += 4; + + /* + * long count + */ + n = p->count; + vp[0] = n>>24; + vp[1] = n>>16; + vp[2] = n>>8; + vp[3] = n; + vp += 4; + + /* + * vlong time + */ + if (havecycles){ + n = (vlong)(p->time / (vlong)khz); + }else + n = p->time; + + vp[0] = n>>24; + vp[1] = n>>16; + vp[2] = n>>8; + vp[3] = n; + vp += 4; + } + write(f, (char*)_tos->prof.first, vp - (char*)_tos->prof.first); + close(f); +} + +void +_profinit(int entries, int what) +{ + if (_tos->prof.what == 0) + return; /* Profiling not linked in */ + _tos->prof.pp = nil; + _tos->prof.first = mallocz(entries*sizeof(Plink),1); + _tos->prof.last = _tos->prof.first + entries; + _tos->prof.next = _tos->prof.first; + _tos->prof.pid = _tos->pid; + _tos->prof.what = what; + _tos->clock = 1; +} + +void +_profmain(void) +{ + char ename[50]; + int n, f; + + n = 2000; + if (_tos->cyclefreq != 0LL){ + khz = _tos->cyclefreq / 1000; /* Report times in milliseconds */ + havecycles = 1; + } + f = open("/env/profsize", OREAD); + if(f >= 0) { + memset(ename, 0, sizeof(ename)); + read(f, ename, sizeof(ename)-1); + close(f); + n = atol(ename); + } + _tos->prof.what = Profuser; + f = open("/env/proftype", OREAD); + if(f >= 0) { + memset(ename, 0, sizeof(ename)); + read(f, ename, sizeof(ename)-1); + close(f); + if (strcmp(ename, "user") == 0) + _tos->prof.what = Profuser; + else if (strcmp(ename, "kernel") == 0) + _tos->prof.what = Profkernel; + else if (strcmp(ename, "elapsed") == 0 || strcmp(ename, "time") == 0) + _tos->prof.what = Proftime; + else if (strcmp(ename, "sample") == 0) + _tos->prof.what = Profsample; + } + _tos->prof.first = sbrk(n*sizeof(Plink)); + _tos->prof.last = sbrk(0); + _tos->prof.next = _tos->prof.first; + _tos->prof.pp = nil; + _tos->prof.pid = _tos->pid; + atexit(_profdump); + _tos->clock = 1; +} + +void prof(void (*fn)(void*), void *arg, int entries, int what) +{ + _profinit(entries, what); + _tos->prof.pp = _tos->prof.next; + fn(arg); + _profdump(); +} + +#pragma profile on + diff --git a/sys/src/libc/port/qsort.c b/sys/src/libc/port/qsort.c new file mode 100755 index 000000000..91c768c77 --- /dev/null +++ b/sys/src/libc/port/qsort.c @@ -0,0 +1,124 @@ +/* + * qsort -- simple quicksort + */ + +#include <u.h> + +typedef +struct +{ + int (*cmp)(void*, void*); + void (*swap)(char*, char*, long); + long es; +} Sort; + +static void +swapb(char *i, char *j, long es) +{ + char c; + + do { + c = *i; + *i++ = *j; + *j++ = c; + es--; + } while(es != 0); + +} + +static void +swapi(char *ii, char *ij, long es) +{ + long *i, *j, c; + + i = (long*)ii; + j = (long*)ij; + do { + c = *i; + *i++ = *j; + *j++ = c; + es -= sizeof(long); + } while(es != 0); +} + +static char* +pivot(char *a, long n, Sort *p) +{ + long j; + char *pi, *pj, *pk; + + j = n/6 * p->es; + pi = a + j; /* 1/6 */ + j += j; + pj = pi + j; /* 1/2 */ + pk = pj + j; /* 5/6 */ + if(p->cmp(pi, pj) < 0) { + if(p->cmp(pi, pk) < 0) { + if(p->cmp(pj, pk) < 0) + return pj; + return pk; + } + return pi; + } + if(p->cmp(pj, pk) < 0) { + if(p->cmp(pi, pk) < 0) + return pi; + return pk; + } + return pj; +} + +static void +qsorts(char *a, long n, Sort *p) +{ + long j, es; + char *pi, *pj, *pn; + + es = p->es; + while(n > 1) { + if(n > 10) { + pi = pivot(a, n, p); + } else + pi = a + (n>>1)*es; + + p->swap(a, pi, es); + pi = a; + pn = a + n*es; + pj = pn; + for(;;) { + do + pi += es; + while(pi < pn && p->cmp(pi, a) < 0); + do + pj -= es; + while(pj > a && p->cmp(pj, a) > 0); + if(pj < pi) + break; + p->swap(pi, pj, es); + } + p->swap(a, pj, es); + j = (pj - a) / es; + + n = n-j-1; + if(j >= n) { + qsorts(a, j, p); + a += (j+1)*es; + } else { + qsorts(a + (j+1)*es, n, p); + n = j; + } + } +} + +void +qsort(void *va, long n, long es, int (*cmp)(void*, void*)) +{ + Sort s; + + s.cmp = cmp; + s.es = es; + s.swap = swapi; + if(((uintptr)va | es) % sizeof(long)) + s.swap = swapb; + qsorts((char*)va, n, &s); +} diff --git a/sys/src/libc/port/quote.c b/sys/src/libc/port/quote.c new file mode 100755 index 000000000..99f70084c --- /dev/null +++ b/sys/src/libc/port/quote.c @@ -0,0 +1,135 @@ +#include <u.h> +#include <libc.h> + +int (*doquote)(int); + +extern int _needsquotes(char*, int*); +extern int _runeneedsquotes(Rune*, int*); + +char* +unquotestrdup(char *s) +{ + char *t, *ret; + int quoting; + + ret = s = strdup(s); /* return unquoted copy */ + if(ret == nil) + return ret; + quoting = 0; + t = s; /* s is output string, t is input string */ + while(*t!='\0' && (quoting || (*t!=' ' && *t!='\t'))){ + if(*t != '\''){ + *s++ = *t++; + continue; + } + /* *t is a quote */ + if(!quoting){ + quoting = 1; + t++; + continue; + } + /* quoting and we're on a quote */ + if(t[1] != '\''){ + /* end of quoted section; absorb closing quote */ + t++; + quoting = 0; + continue; + } + /* doubled quote; fold one quote into two */ + t++; + *s++ = *t++; + } + if(t != s) + memmove(s, t, strlen(t)+1); + return ret; +} + +Rune* +unquoterunestrdup(Rune *s) +{ + Rune *t, *ret; + int quoting; + + ret = s = runestrdup(s); /* return unquoted copy */ + if(ret == nil) + return ret; + quoting = 0; + t = s; /* s is output string, t is input string */ + while(*t!='\0' && (quoting || (*t!=' ' && *t!='\t'))){ + if(*t != '\''){ + *s++ = *t++; + continue; + } + /* *t is a quote */ + if(!quoting){ + quoting = 1; + t++; + continue; + } + /* quoting and we're on a quote */ + if(t[1] != '\''){ + /* end of quoted section; absorb closing quote */ + t++; + quoting = 0; + continue; + } + /* doubled quote; fold one quote into two */ + t++; + *s++ = *t++; + } + if(t != s) + memmove(s, t, (runestrlen(t)+1)*sizeof(Rune)); + return ret; +} + +char* +quotestrdup(char *s) +{ + char *t, *u, *ret; + int quotelen; + Rune r; + + if(_needsquotes(s, "elen) == 0) + return strdup(s); + + ret = malloc(quotelen+1); + if(ret == nil) + return nil; + u = ret; + *u++ = '\''; + for(t=s; *t; t++){ + r = *t; + if(r == L'\'') + *u++ = r; /* double the quote */ + *u++ = r; + } + *u++ = '\''; + *u = '\0'; + return ret; +} + +Rune* +quoterunestrdup(Rune *s) +{ + Rune *t, *u, *ret; + int quotelen; + Rune r; + + if(_runeneedsquotes(s, "elen) == 0) + return runestrdup(s); + + ret = malloc((quotelen+1)*sizeof(Rune)); + if(ret == nil) + return nil; + u = ret; + *u++ = '\''; + for(t=s; *t; t++){ + r = *t; + if(r == L'\'') + *u++ = r; /* double the quote */ + *u++ = r; + } + *u++ = '\''; + *u = '\0'; + return ret; +} diff --git a/sys/src/libc/port/rand.c b/sys/src/libc/port/rand.c new file mode 100755 index 000000000..366e9e967 --- /dev/null +++ b/sys/src/libc/port/rand.c @@ -0,0 +1,8 @@ +#include <u.h> +#include <libc.h> + +int +rand(void) +{ + return lrand() & 0x7fff; +} diff --git a/sys/src/libc/port/readn.c b/sys/src/libc/port/readn.c new file mode 100755 index 000000000..629dfd9ed --- /dev/null +++ b/sys/src/libc/port/readn.c @@ -0,0 +1,22 @@ +#include <u.h> +#include <libc.h> + +long +readn(int f, void *av, long n) +{ + char *a; + long m, t; + + a = av; + t = 0; + while(t < n){ + m = read(f, a+t, n-t); + if(m <= 0){ + if(t == 0) + return m; + break; + } + t += m; + } + return t; +} diff --git a/sys/src/libc/port/reduce b/sys/src/libc/port/reduce new file mode 100755 index 000000000..584f8b9ab --- /dev/null +++ b/sys/src/libc/port/reduce @@ -0,0 +1,16 @@ +O=$1 +shift +objtype=$1 +shift + +ls -p ../$objtype/*.[cs] >[2]/dev/null | sed 's/..$//;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 diff --git a/sys/src/libc/port/rune.c b/sys/src/libc/port/rune.c new file mode 100755 index 000000000..b62da9e66 --- /dev/null +++ b/sys/src/libc/port/rune.c @@ -0,0 +1,162 @@ +#include <u.h> +#include <libc.h> + +enum +{ + Bit1 = 7, + Bitx = 6, + Bit2 = 5, + Bit3 = 4, + Bit4 = 3, + + 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 */ + + Rune1 = (1<<(Bit1+0*Bitx))-1, /* 0000 0000 0111 1111 */ + Rune2 = (1<<(Bit2+1*Bitx))-1, /* 0000 0111 1111 1111 */ + Rune3 = (1<<(Bit3+2*Bitx))-1, /* 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; + 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; + } + + /* + * bad decoding + */ +bad: + *rune = Bad; + return 1; +} + +int +runetochar(char *str, Rune *rune) +{ + long c; + + /* + * one character sequence + * 00000-0007F => 00-7F + */ + c = *rune; + 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 + */ + str[0] = T3 | (c >> 2*Bitx); + str[1] = Tx | ((c >> 1*Bitx) & Maskx); + str[2] = Tx | (c & Maskx); + return 3; +} + +int +runelen(long c) +{ + Rune rune; + char str[10]; + + 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 + nb += 3; + } + return nb; +} + +int +fullrune(char *str, int n) +{ + int c; + + if(n > 0) { + c = *(uchar*)str; + if(c < Tx) + return 1; + if(n > 1) + if(c < T3 || n > 2) + return 1; + } + return 0; +} diff --git a/sys/src/libc/port/runestrcat.c b/sys/src/libc/port/runestrcat.c new file mode 100755 index 000000000..4c8363067 --- /dev/null +++ b/sys/src/libc/port/runestrcat.c @@ -0,0 +1,10 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrcat(Rune *s1, Rune *s2) +{ + + runestrcpy(runestrchr(s1, 0), s2); + return s1; +} diff --git a/sys/src/libc/port/runestrchr.c b/sys/src/libc/port/runestrchr.c new file mode 100755 index 000000000..af7fc4e88 --- /dev/null +++ b/sys/src/libc/port/runestrchr.c @@ -0,0 +1,20 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrchr(Rune *s, Rune c) +{ + Rune c0 = c; + Rune c1; + + if(c == 0) { + while(*s++) + ; + return s-1; + } + + while(c1 = *s++) + if(c1 == c0) + return s-1; + return 0; +} diff --git a/sys/src/libc/port/runestrcmp.c b/sys/src/libc/port/runestrcmp.c new file mode 100755 index 000000000..e3bda3738 --- /dev/null +++ b/sys/src/libc/port/runestrcmp.c @@ -0,0 +1,20 @@ +#include <u.h> +#include <libc.h> + +int +runestrcmp(Rune *s1, Rune *s2) +{ + Rune c1, c2; + + for(;;) { + c1 = *s1++; + c2 = *s2++; + if(c1 != c2) { + if(c1 > c2) + return 1; + return -1; + } + if(c1 == 0) + return 0; + } +} diff --git a/sys/src/libc/port/runestrcpy.c b/sys/src/libc/port/runestrcpy.c new file mode 100755 index 000000000..efddc0734 --- /dev/null +++ b/sys/src/libc/port/runestrcpy.c @@ -0,0 +1,13 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrcpy(Rune *s1, Rune *s2) +{ + Rune *os1; + + os1 = s1; + while(*s1++ = *s2++) + ; + return os1; +} diff --git a/sys/src/libc/port/runestrdup.c b/sys/src/libc/port/runestrdup.c new file mode 100755 index 000000000..f66b430b6 --- /dev/null +++ b/sys/src/libc/port/runestrdup.c @@ -0,0 +1,14 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrdup(Rune *s) +{ + Rune *ns; + + ns = malloc(sizeof(Rune)*(runestrlen(s) + 1)); + if(ns == 0) + return 0; + + return runestrcpy(ns, s); +} diff --git a/sys/src/libc/port/runestrecpy.c b/sys/src/libc/port/runestrecpy.c new file mode 100755 index 000000000..d3ca81044 --- /dev/null +++ b/sys/src/libc/port/runestrecpy.c @@ -0,0 +1,17 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrecpy(Rune *s1, Rune *es1, Rune *s2) +{ + if(s1 >= es1) + return s1; + + while(*s1++ = *s2++){ + if(s1 == es1){ + *--s1 = '\0'; + break; + } + } + return s1; +} diff --git a/sys/src/libc/port/runestrlen.c b/sys/src/libc/port/runestrlen.c new file mode 100755 index 000000000..2bf4a4eb6 --- /dev/null +++ b/sys/src/libc/port/runestrlen.c @@ -0,0 +1,9 @@ +#include <u.h> +#include <libc.h> + +long +runestrlen(Rune *s) +{ + + return runestrchr(s, 0) - s; +} diff --git a/sys/src/libc/port/runestrncat.c b/sys/src/libc/port/runestrncat.c new file mode 100755 index 000000000..9d6ee46a6 --- /dev/null +++ b/sys/src/libc/port/runestrncat.c @@ -0,0 +1,17 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrncat(Rune *s1, Rune *s2, long n) +{ + Rune *os1; + + os1 = s1; + s1 = runestrchr(s1, 0); + while(*s1++ = *s2++) + if(--n < 0) { + s1[-1] = 0; + break; + } + return os1; +} diff --git a/sys/src/libc/port/runestrncmp.c b/sys/src/libc/port/runestrncmp.c new file mode 100755 index 000000000..5e566fa0c --- /dev/null +++ b/sys/src/libc/port/runestrncmp.c @@ -0,0 +1,22 @@ +#include <u.h> +#include <libc.h> + +int +runestrncmp(Rune *s1, Rune *s2, long n) +{ + Rune c1, c2; + + while(n > 0) { + c1 = *s1++; + c2 = *s2++; + n--; + if(c1 != c2) { + if(c1 > c2) + return 1; + return -1; + } + if(c1 == 0) + break; + } + return 0; +} diff --git a/sys/src/libc/port/runestrncpy.c b/sys/src/libc/port/runestrncpy.c new file mode 100755 index 000000000..7e84e33f7 --- /dev/null +++ b/sys/src/libc/port/runestrncpy.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrncpy(Rune *s1, Rune *s2, long n) +{ + int i; + Rune *os1; + + os1 = s1; + for(i = 0; i < n; i++) + if((*s1++ = *s2++) == 0) { + while(++i < n) + *s1++ = 0; + return os1; + } + return os1; +} diff --git a/sys/src/libc/port/runestrrchr.c b/sys/src/libc/port/runestrrchr.c new file mode 100755 index 000000000..4c8074ba0 --- /dev/null +++ b/sys/src/libc/port/runestrrchr.c @@ -0,0 +1,15 @@ +#include <u.h> +#include <libc.h> + +Rune* +runestrrchr(Rune *s, Rune c) +{ + Rune *r; + + if(c == 0) + return runestrchr(s, 0); + r = 0; + while(s = runestrchr(s, c)) + r = s++; + return r; +} diff --git a/sys/src/libc/port/runestrstr.c b/sys/src/libc/port/runestrstr.c new file mode 100755 index 000000000..b7f6964b2 --- /dev/null +++ b/sys/src/libc/port/runestrstr.c @@ -0,0 +1,29 @@ +#include <u.h> +#include <libc.h> + +/* + * Return pointer to first occurrence of s2 in s1, + * 0 if none + */ +Rune* +runestrstr(Rune *s1, Rune *s2) +{ + Rune *p, *pa, *pb; + int c0, c; + + c0 = *s2; + if(c0 == 0) + return s1; + s2++; + for(p=runestrchr(s1, c0); p; p=runestrchr(p+1, c0)) { + pa = p; + for(pb=s2;; pb++) { + c = *pb; + if(c == 0) + return p; + if(c != *++pa) + break; + } + } + return 0; +} diff --git a/sys/src/libc/port/runetype.c b/sys/src/libc/port/runetype.c new file mode 100755 index 000000000..f7ec1bb98 --- /dev/null +++ b/sys/src/libc/port/runetype.c @@ -0,0 +1,1181 @@ +#include <u.h> +#include <libc.h> + +/* + * alpha ranges - + * only covers ranges not in lower||upper + */ +static +Rune _alpha2[] = +{ + 0x00d8, 0x00f6, /* Ø - ö */ + 0x00f8, 0x01f5, /* ø - ǵ */ + 0x0250, 0x02a8, /* ɐ - ʨ */ + 0x038e, 0x03a1, /* Ύ - Ρ */ + 0x03a3, 0x03ce, /* Σ - ώ */ + 0x03d0, 0x03d6, /* ϐ - ϖ */ + 0x03e2, 0x03f3, /* Ϣ - ϳ */ + 0x0490, 0x04c4, /* Ґ - ӄ */ + 0x0561, 0x0587, /* ա - և */ + 0x05d0, 0x05ea, /* א - ת */ + 0x05f0, 0x05f2, /* װ - ײ */ + 0x0621, 0x063a, /* ء - غ */ + 0x0640, 0x064a, /* ـ - ي */ + 0x0671, 0x06b7, /* ٱ - ڷ */ + 0x06ba, 0x06be, /* ں - ھ */ + 0x06c0, 0x06ce, /* ۀ - ێ */ + 0x06d0, 0x06d3, /* ې - ۓ */ + 0x0905, 0x0939, /* अ - ह */ + 0x0958, 0x0961, /* क़ - ॡ */ + 0x0985, 0x098c, /* অ - ঌ */ + 0x098f, 0x0990, /* এ - ঐ */ + 0x0993, 0x09a8, /* ও - ন */ + 0x09aa, 0x09b0, /* প - র */ + 0x09b6, 0x09b9, /* শ - হ */ + 0x09dc, 0x09dd, /* ড় - ঢ় */ + 0x09df, 0x09e1, /* য় - ৡ */ + 0x09f0, 0x09f1, /* ৰ - ৱ */ + 0x0a05, 0x0a0a, /* ਅ - ਊ */ + 0x0a0f, 0x0a10, /* ਏ - ਐ */ + 0x0a13, 0x0a28, /* ਓ - ਨ */ + 0x0a2a, 0x0a30, /* ਪ - ਰ */ + 0x0a32, 0x0a33, /* ਲ - ਲ਼ */ + 0x0a35, 0x0a36, /* ਵ - ਸ਼ */ + 0x0a38, 0x0a39, /* ਸ - ਹ */ + 0x0a59, 0x0a5c, /* ਖ਼ - ੜ */ + 0x0a85, 0x0a8b, /* અ - ઋ */ + 0x0a8f, 0x0a91, /* એ - ઑ */ + 0x0a93, 0x0aa8, /* ઓ - ન */ + 0x0aaa, 0x0ab0, /* પ - ર */ + 0x0ab2, 0x0ab3, /* લ - ળ */ + 0x0ab5, 0x0ab9, /* વ - હ */ + 0x0b05, 0x0b0c, /* ଅ - ଌ */ + 0x0b0f, 0x0b10, /* ଏ - ଐ */ + 0x0b13, 0x0b28, /* ଓ - ନ */ + 0x0b2a, 0x0b30, /* ପ - ର */ + 0x0b32, 0x0b33, /* ଲ - ଳ */ + 0x0b36, 0x0b39, /* ଶ - ହ */ + 0x0b5c, 0x0b5d, /* ଡ଼ - ଢ଼ */ + 0x0b5f, 0x0b61, /* ୟ - ୡ */ + 0x0b85, 0x0b8a, /* அ - ஊ */ + 0x0b8e, 0x0b90, /* எ - ஐ */ + 0x0b92, 0x0b95, /* ஒ - க */ + 0x0b99, 0x0b9a, /* ங - ச */ + 0x0b9e, 0x0b9f, /* ஞ - ட */ + 0x0ba3, 0x0ba4, /* ண - த */ + 0x0ba8, 0x0baa, /* ந - ப */ + 0x0bae, 0x0bb5, /* ம - வ */ + 0x0bb7, 0x0bb9, /* ஷ - ஹ */ + 0x0c05, 0x0c0c, /* అ - ఌ */ + 0x0c0e, 0x0c10, /* ఎ - ఐ */ + 0x0c12, 0x0c28, /* ఒ - న */ + 0x0c2a, 0x0c33, /* ప - ళ */ + 0x0c35, 0x0c39, /* వ - హ */ + 0x0c60, 0x0c61, /* ౠ - ౡ */ + 0x0c85, 0x0c8c, /* ಅ - ಌ */ + 0x0c8e, 0x0c90, /* ಎ - ಐ */ + 0x0c92, 0x0ca8, /* ಒ - ನ */ + 0x0caa, 0x0cb3, /* ಪ - ಳ */ + 0x0cb5, 0x0cb9, /* ವ - ಹ */ + 0x0ce0, 0x0ce1, /* ೠ - ೡ */ + 0x0d05, 0x0d0c, /* അ - ഌ */ + 0x0d0e, 0x0d10, /* എ - ഐ */ + 0x0d12, 0x0d28, /* ഒ - ന */ + 0x0d2a, 0x0d39, /* പ - ഹ */ + 0x0d60, 0x0d61, /* ൠ - ൡ */ + 0x0e01, 0x0e30, /* ก - ะ */ + 0x0e32, 0x0e33, /* า - ำ */ + 0x0e40, 0x0e46, /* เ - ๆ */ + 0x0e5a, 0x0e5b, /* ๚ - ๛ */ + 0x0e81, 0x0e82, /* ກ - ຂ */ + 0x0e87, 0x0e88, /* ງ - ຈ */ + 0x0e94, 0x0e97, /* ດ - ທ */ + 0x0e99, 0x0e9f, /* ນ - ຟ */ + 0x0ea1, 0x0ea3, /* ມ - ຣ */ + 0x0eaa, 0x0eab, /* ສ - ຫ */ + 0x0ead, 0x0eae, /* ອ - ຮ */ + 0x0eb2, 0x0eb3, /* າ - ຳ */ + 0x0ec0, 0x0ec4, /* ເ - ໄ */ + 0x0edc, 0x0edd, /* ໜ - ໝ */ + 0x0f18, 0x0f19, /* ༘ - ༙ */ + 0x0f40, 0x0f47, /* ཀ - ཇ */ + 0x0f49, 0x0f69, /* ཉ - ཀྵ */ + 0x10d0, 0x10f6, /* ა - ჶ */ + 0x1100, 0x1159, /* ᄀ - ᅙ */ + 0x115f, 0x11a2, /* ᅟ - ᆢ */ + 0x11a8, 0x11f9, /* ᆨ - ᇹ */ + 0x1e00, 0x1e9b, /* Ḁ - ẛ */ + 0x1f50, 0x1f57, /* ὐ - ὗ */ + 0x1f80, 0x1fb4, /* ᾀ - ᾴ */ + 0x1fb6, 0x1fbc, /* ᾶ - ᾼ */ + 0x1fc2, 0x1fc4, /* ῂ - ῄ */ + 0x1fc6, 0x1fcc, /* ῆ - ῌ */ + 0x1fd0, 0x1fd3, /* ῐ - ΐ */ + 0x1fd6, 0x1fdb, /* ῖ - Ί */ + 0x1fe0, 0x1fec, /* ῠ - Ῥ */ + 0x1ff2, 0x1ff4, /* ῲ - ῴ */ + 0x1ff6, 0x1ffc, /* ῶ - ῼ */ + 0x210a, 0x2113, /* ℊ - ℓ */ + 0x2115, 0x211d, /* ℕ - ℝ */ + 0x2120, 0x2122, /* ℠ - ™ */ + 0x212a, 0x2131, /* K - ℱ */ + 0x2133, 0x2138, /* ℳ - ℸ */ + 0x3041, 0x3094, /* ぁ - ゔ */ + 0x30a1, 0x30fa, /* ァ - ヺ */ + 0x3105, 0x312c, /* ㄅ - ㄬ */ + 0x3131, 0x318e, /* ㄱ - ㆎ */ + 0x3192, 0x319f, /* ㆒ - ㆟ */ + 0x3260, 0x327b, /* ㉠ - ㉻ */ + 0x328a, 0x32b0, /* ㊊ - ㊰ */ + 0x32d0, 0x32fe, /* ㋐ - ㋾ */ + 0x3300, 0x3357, /* ㌀ - ㍗ */ + 0x3371, 0x3376, /* ㍱ - ㍶ */ + 0x337b, 0x3394, /* ㍻ - ㎔ */ + 0x3399, 0x339e, /* ㎙ - ㎞ */ + 0x33a9, 0x33ad, /* ㎩ - ㎭ */ + 0x33b0, 0x33c1, /* ㎰ - ㏁ */ + 0x33c3, 0x33c5, /* ㏃ - ㏅ */ + 0x33c7, 0x33d7, /* ㏇ - ㏗ */ + 0x33d9, 0x33dd, /* ㏙ - ㏝ */ + 0x4e00, 0x9fff, /* 一 - 鿿 */ + 0xac00, 0xd7a3, /* 가 - 힣 */ + 0xf900, 0xfb06, /* 豈 - st */ + 0xfb13, 0xfb17, /* ﬓ - ﬗ */ + 0xfb1f, 0xfb28, /* ײַ - ﬨ */ + 0xfb2a, 0xfb36, /* שׁ - זּ */ + 0xfb38, 0xfb3c, /* טּ - לּ */ + 0xfb40, 0xfb41, /* נּ - סּ */ + 0xfb43, 0xfb44, /* ףּ - פּ */ + 0xfb46, 0xfbb1, /* צּ - ﮱ */ + 0xfbd3, 0xfd3d, /* ﯓ - ﴽ */ + 0xfd50, 0xfd8f, /* ﵐ - ﶏ */ + 0xfd92, 0xfdc7, /* ﶒ - ﷇ */ + 0xfdf0, 0xfdf9, /* ﷰ - ﷹ */ + 0xfe70, 0xfe72, /* ﹰ - ﹲ */ + 0xfe76, 0xfefc, /* ﹶ - ﻼ */ + 0xff66, 0xff6f, /* ヲ - ッ */ + 0xff71, 0xff9d, /* ア - ン */ + 0xffa0, 0xffbe, /* ᅠ - ᄒ */ + 0xffc2, 0xffc7, /* ᅡ - ᅦ */ + 0xffca, 0xffcf, /* ᅧ - ᅬ */ + 0xffd2, 0xffd7, /* ᅭ - ᅲ */ + 0xffda, 0xffdc, /* ᅳ - ᅵ */ +}; + +/* + * alpha singlets - + * only covers ranges not in lower||upper + */ +static +Rune _alpha1[] = +{ + 0x00aa, /* ª */ + 0x00b5, /* µ */ + 0x00ba, /* º */ + 0x03da, /* Ϛ */ + 0x03dc, /* Ϝ */ + 0x03de, /* Ϟ */ + 0x03e0, /* Ϡ */ + 0x06d5, /* ە */ + 0x09b2, /* ল */ + 0x0a5e, /* ਫ਼ */ + 0x0a8d, /* ઍ */ + 0x0ae0, /* ૠ */ + 0x0b9c, /* ஜ */ + 0x0cde, /* ೞ */ + 0x0e4f, /* ๏ */ + 0x0e84, /* ຄ */ + 0x0e8a, /* ຊ */ + 0x0e8d, /* ຍ */ + 0x0ea5, /* ລ */ + 0x0ea7, /* ວ */ + 0x0eb0, /* ະ */ + 0x0ebd, /* ຽ */ + 0x1fbe, /* ι */ + 0x207f, /* ⁿ */ + 0x20a8, /* ₨ */ + 0x2102, /* ℂ */ + 0x2107, /* ℇ */ + 0x2124, /* ℤ */ + 0x2126, /* Ω */ + 0x2128, /* ℨ */ + 0xfb3e, /* מּ */ + 0xfe74, /* ﹴ */ +}; + +/* + * space ranges + */ +static +Rune _space2[] = +{ + 0x0009, 0x000a, /* tab and newline */ + 0x0020, 0x0020, /* space */ + 0x0085, 0x0085, + 0x00a0, 0x00a0, /* */ + 0x1680, 0x1680, + 0x180e, 0x180e, + 0x2000, 0x200b, /* - */ + 0x2028, 0x2029, /*
-
*/ + 0x202f, 0x202f, + 0x205f, 0x205f, + 0x3000, 0x3000, /* */ + 0xfeff, 0xfeff, /* */ +}; + +/* + * lower case ranges + * 3rd col is conversion excess 500 + */ +static +Rune _toupper2[] = +{ + 0x0061, 0x007a, 468, /* a-z A-Z */ + 0x00e0, 0x00f6, 468, /* à-ö À-Ö */ + 0x00f8, 0x00fe, 468, /* ø-þ Ø-Þ */ + 0x0256, 0x0257, 295, /* ɖ-ɗ Ɖ-Ɗ */ + 0x0258, 0x0259, 298, /* ɘ-ə Ǝ-Ə */ + 0x028a, 0x028b, 283, /* ʊ-ʋ Ʊ-Ʋ */ + 0x03ad, 0x03af, 463, /* έ-ί Έ-Ί */ + 0x03b1, 0x03c1, 468, /* α-ρ Α-Ρ */ + 0x03c3, 0x03cb, 468, /* σ-ϋ Σ-Ϋ */ + 0x03cd, 0x03ce, 437, /* ύ-ώ Ύ-Ώ */ + 0x0430, 0x044f, 468, /* а-я А-Я */ + 0x0451, 0x045c, 420, /* ё-ќ Ё-Ќ */ + 0x045e, 0x045f, 420, /* ў-џ Ў-Џ */ + 0x0561, 0x0586, 452, /* ա-ֆ Ա-Ֆ */ + 0x1f00, 0x1f07, 508, /* ἀ-ἇ Ἀ-Ἇ */ + 0x1f10, 0x1f15, 508, /* ἐ-ἕ Ἐ-Ἕ */ + 0x1f20, 0x1f27, 508, /* ἠ-ἧ Ἠ-Ἧ */ + 0x1f30, 0x1f37, 508, /* ἰ-ἷ Ἰ-Ἷ */ + 0x1f40, 0x1f45, 508, /* ὀ-ὅ Ὀ-Ὅ */ + 0x1f60, 0x1f67, 508, /* ὠ-ὧ Ὠ-Ὧ */ + 0x1f70, 0x1f71, 574, /* ὰ-ά Ὰ-Ά */ + 0x1f72, 0x1f75, 586, /* ὲ-ή Ὲ-Ή */ + 0x1f76, 0x1f77, 600, /* ὶ-ί Ὶ-Ί */ + 0x1f78, 0x1f79, 628, /* ὸ-ό Ὸ-Ό */ + 0x1f7a, 0x1f7b, 612, /* ὺ-ύ Ὺ-Ύ */ + 0x1f7c, 0x1f7d, 626, /* ὼ-ώ Ὼ-Ώ */ + 0x1f80, 0x1f87, 508, /* ᾀ-ᾇ ᾈ-ᾏ */ + 0x1f90, 0x1f97, 508, /* ᾐ-ᾗ ᾘ-ᾟ */ + 0x1fa0, 0x1fa7, 508, /* ᾠ-ᾧ ᾨ-ᾯ */ + 0x1fb0, 0x1fb1, 508, /* ᾰ-ᾱ Ᾰ-Ᾱ */ + 0x1fd0, 0x1fd1, 508, /* ῐ-ῑ Ῐ-Ῑ */ + 0x1fe0, 0x1fe1, 508, /* ῠ-ῡ Ῠ-Ῡ */ + 0x2170, 0x217f, 484, /* ⅰ-ⅿ Ⅰ-Ⅿ */ + 0x24d0, 0x24e9, 474, /* ⓐ-ⓩ Ⓐ-Ⓩ */ + 0xff41, 0xff5a, 468, /* a-z A-Z */ +}; + +/* + * lower case singlets + * 2nd col is conversion excess 500 + */ +static +Rune _toupper1[] = +{ + 0x00ff, 621, /* ÿ Ÿ */ + 0x0101, 499, /* ā Ā */ + 0x0103, 499, /* ă Ă */ + 0x0105, 499, /* ą Ą */ + 0x0107, 499, /* ć Ć */ + 0x0109, 499, /* ĉ Ĉ */ + 0x010b, 499, /* ċ Ċ */ + 0x010d, 499, /* č Č */ + 0x010f, 499, /* ď Ď */ + 0x0111, 499, /* đ Đ */ + 0x0113, 499, /* ē Ē */ + 0x0115, 499, /* ĕ Ĕ */ + 0x0117, 499, /* ė Ė */ + 0x0119, 499, /* ę Ę */ + 0x011b, 499, /* ě Ě */ + 0x011d, 499, /* ĝ Ĝ */ + 0x011f, 499, /* ğ Ğ */ + 0x0121, 499, /* ġ Ġ */ + 0x0123, 499, /* ģ Ģ */ + 0x0125, 499, /* ĥ Ĥ */ + 0x0127, 499, /* ħ Ħ */ + 0x0129, 499, /* ĩ Ĩ */ + 0x012b, 499, /* ī Ī */ + 0x012d, 499, /* ĭ Ĭ */ + 0x012f, 499, /* į Į */ + 0x0131, 268, /* ı I */ + 0x0133, 499, /* ij IJ */ + 0x0135, 499, /* ĵ Ĵ */ + 0x0137, 499, /* ķ Ķ */ + 0x013a, 499, /* ĺ Ĺ */ + 0x013c, 499, /* ļ Ļ */ + 0x013e, 499, /* ľ Ľ */ + 0x0140, 499, /* ŀ Ŀ */ + 0x0142, 499, /* ł Ł */ + 0x0144, 499, /* ń Ń */ + 0x0146, 499, /* ņ Ņ */ + 0x0148, 499, /* ň Ň */ + 0x014b, 499, /* ŋ Ŋ */ + 0x014d, 499, /* ō Ō */ + 0x014f, 499, /* ŏ Ŏ */ + 0x0151, 499, /* ő Ő */ + 0x0153, 499, /* œ Œ */ + 0x0155, 499, /* ŕ Ŕ */ + 0x0157, 499, /* ŗ Ŗ */ + 0x0159, 499, /* ř Ř */ + 0x015b, 499, /* ś Ś */ + 0x015d, 499, /* ŝ Ŝ */ + 0x015f, 499, /* ş Ş */ + 0x0161, 499, /* š Š */ + 0x0163, 499, /* ţ Ţ */ + 0x0165, 499, /* ť Ť */ + 0x0167, 499, /* ŧ Ŧ */ + 0x0169, 499, /* ũ Ũ */ + 0x016b, 499, /* ū Ū */ + 0x016d, 499, /* ŭ Ŭ */ + 0x016f, 499, /* ů Ů */ + 0x0171, 499, /* ű Ű */ + 0x0173, 499, /* ų Ų */ + 0x0175, 499, /* ŵ Ŵ */ + 0x0177, 499, /* ŷ Ŷ */ + 0x017a, 499, /* ź Ź */ + 0x017c, 499, /* ż Ż */ + 0x017e, 499, /* ž Ž */ + 0x017f, 200, /* ſ S */ + 0x0183, 499, /* ƃ Ƃ */ + 0x0185, 499, /* ƅ Ƅ */ + 0x0188, 499, /* ƈ Ƈ */ + 0x018c, 499, /* ƌ Ƌ */ + 0x0192, 499, /* ƒ Ƒ */ + 0x0199, 499, /* ƙ Ƙ */ + 0x01a1, 499, /* ơ Ơ */ + 0x01a3, 499, /* ƣ Ƣ */ + 0x01a5, 499, /* ƥ Ƥ */ + 0x01a8, 499, /* ƨ Ƨ */ + 0x01ad, 499, /* ƭ Ƭ */ + 0x01b0, 499, /* ư Ư */ + 0x01b4, 499, /* ƴ Ƴ */ + 0x01b6, 499, /* ƶ Ƶ */ + 0x01b9, 499, /* ƹ Ƹ */ + 0x01bd, 499, /* ƽ Ƽ */ + 0x01c5, 499, /* Dž DŽ */ + 0x01c6, 498, /* dž DŽ */ + 0x01c8, 499, /* Lj LJ */ + 0x01c9, 498, /* lj LJ */ + 0x01cb, 499, /* Nj NJ */ + 0x01cc, 498, /* nj NJ */ + 0x01ce, 499, /* ǎ Ǎ */ + 0x01d0, 499, /* ǐ Ǐ */ + 0x01d2, 499, /* ǒ Ǒ */ + 0x01d4, 499, /* ǔ Ǔ */ + 0x01d6, 499, /* ǖ Ǖ */ + 0x01d8, 499, /* ǘ Ǘ */ + 0x01da, 499, /* ǚ Ǚ */ + 0x01dc, 499, /* ǜ Ǜ */ + 0x01df, 499, /* ǟ Ǟ */ + 0x01e1, 499, /* ǡ Ǡ */ + 0x01e3, 499, /* ǣ Ǣ */ + 0x01e5, 499, /* ǥ Ǥ */ + 0x01e7, 499, /* ǧ Ǧ */ + 0x01e9, 499, /* ǩ Ǩ */ + 0x01eb, 499, /* ǫ Ǫ */ + 0x01ed, 499, /* ǭ Ǭ */ + 0x01ef, 499, /* ǯ Ǯ */ + 0x01f2, 499, /* Dz DZ */ + 0x01f3, 498, /* dz DZ */ + 0x01f5, 499, /* ǵ Ǵ */ + 0x01fb, 499, /* ǻ Ǻ */ + 0x01fd, 499, /* ǽ Ǽ */ + 0x01ff, 499, /* ǿ Ǿ */ + 0x0201, 499, /* ȁ Ȁ */ + 0x0203, 499, /* ȃ Ȃ */ + 0x0205, 499, /* ȅ Ȅ */ + 0x0207, 499, /* ȇ Ȇ */ + 0x0209, 499, /* ȉ Ȉ */ + 0x020b, 499, /* ȋ Ȋ */ + 0x020d, 499, /* ȍ Ȍ */ + 0x020f, 499, /* ȏ Ȏ */ + 0x0211, 499, /* ȑ Ȑ */ + 0x0213, 499, /* ȓ Ȓ */ + 0x0215, 499, /* ȕ Ȕ */ + 0x0217, 499, /* ȗ Ȗ */ + 0x0253, 290, /* ɓ Ɓ */ + 0x0254, 294, /* ɔ Ɔ */ + 0x025b, 297, /* ɛ Ɛ */ + 0x0260, 295, /* ɠ Ɠ */ + 0x0263, 293, /* ɣ Ɣ */ + 0x0268, 291, /* ɨ Ɨ */ + 0x0269, 289, /* ɩ Ɩ */ + 0x026f, 289, /* ɯ Ɯ */ + 0x0272, 287, /* ɲ Ɲ */ + 0x0283, 282, /* ʃ Ʃ */ + 0x0288, 282, /* ʈ Ʈ */ + 0x0292, 281, /* ʒ Ʒ */ + 0x03ac, 462, /* ά Ά */ + 0x03cc, 436, /* ό Ό */ + 0x03d0, 438, /* ϐ Β */ + 0x03d1, 443, /* ϑ Θ */ + 0x03d5, 453, /* ϕ Φ */ + 0x03d6, 446, /* ϖ Π */ + 0x03e3, 499, /* ϣ Ϣ */ + 0x03e5, 499, /* ϥ Ϥ */ + 0x03e7, 499, /* ϧ Ϧ */ + 0x03e9, 499, /* ϩ Ϩ */ + 0x03eb, 499, /* ϫ Ϫ */ + 0x03ed, 499, /* ϭ Ϭ */ + 0x03ef, 499, /* ϯ Ϯ */ + 0x03f0, 414, /* ϰ Κ */ + 0x03f1, 420, /* ϱ Ρ */ + 0x0461, 499, /* ѡ Ѡ */ + 0x0463, 499, /* ѣ Ѣ */ + 0x0465, 499, /* ѥ Ѥ */ + 0x0467, 499, /* ѧ Ѧ */ + 0x0469, 499, /* ѩ Ѩ */ + 0x046b, 499, /* ѫ Ѫ */ + 0x046d, 499, /* ѭ Ѭ */ + 0x046f, 499, /* ѯ Ѯ */ + 0x0471, 499, /* ѱ Ѱ */ + 0x0473, 499, /* ѳ Ѳ */ + 0x0475, 499, /* ѵ Ѵ */ + 0x0477, 499, /* ѷ Ѷ */ + 0x0479, 499, /* ѹ Ѹ */ + 0x047b, 499, /* ѻ Ѻ */ + 0x047d, 499, /* ѽ Ѽ */ + 0x047f, 499, /* ѿ Ѿ */ + 0x0481, 499, /* ҁ Ҁ */ + 0x0491, 499, /* ґ Ґ */ + 0x0493, 499, /* ғ Ғ */ + 0x0495, 499, /* ҕ Ҕ */ + 0x0497, 499, /* җ Җ */ + 0x0499, 499, /* ҙ Ҙ */ + 0x049b, 499, /* қ Қ */ + 0x049d, 499, /* ҝ Ҝ */ + 0x049f, 499, /* ҟ Ҟ */ + 0x04a1, 499, /* ҡ Ҡ */ + 0x04a3, 499, /* ң Ң */ + 0x04a5, 499, /* ҥ Ҥ */ + 0x04a7, 499, /* ҧ Ҧ */ + 0x04a9, 499, /* ҩ Ҩ */ + 0x04ab, 499, /* ҫ Ҫ */ + 0x04ad, 499, /* ҭ Ҭ */ + 0x04af, 499, /* ү Ү */ + 0x04b1, 499, /* ұ Ұ */ + 0x04b3, 499, /* ҳ Ҳ */ + 0x04b5, 499, /* ҵ Ҵ */ + 0x04b7, 499, /* ҷ Ҷ */ + 0x04b9, 499, /* ҹ Ҹ */ + 0x04bb, 499, /* һ Һ */ + 0x04bd, 499, /* ҽ Ҽ */ + 0x04bf, 499, /* ҿ Ҿ */ + 0x04c2, 499, /* ӂ Ӂ */ + 0x04c4, 499, /* ӄ Ӄ */ + 0x04c8, 499, /* ӈ Ӈ */ + 0x04cc, 499, /* ӌ Ӌ */ + 0x04d1, 499, /* ӑ Ӑ */ + 0x04d3, 499, /* ӓ Ӓ */ + 0x04d5, 499, /* ӕ Ӕ */ + 0x04d7, 499, /* ӗ Ӗ */ + 0x04d9, 499, /* ә Ә */ + 0x04db, 499, /* ӛ Ӛ */ + 0x04dd, 499, /* ӝ Ӝ */ + 0x04df, 499, /* ӟ Ӟ */ + 0x04e1, 499, /* ӡ Ӡ */ + 0x04e3, 499, /* ӣ Ӣ */ + 0x04e5, 499, /* ӥ Ӥ */ + 0x04e7, 499, /* ӧ Ӧ */ + 0x04e9, 499, /* ө Ө */ + 0x04eb, 499, /* ӫ Ӫ */ + 0x04ef, 499, /* ӯ Ӯ */ + 0x04f1, 499, /* ӱ Ӱ */ + 0x04f3, 499, /* ӳ Ӳ */ + 0x04f5, 499, /* ӵ Ӵ */ + 0x04f9, 499, /* ӹ Ӹ */ + 0x1e01, 499, /* ḁ Ḁ */ + 0x1e03, 499, /* ḃ Ḃ */ + 0x1e05, 499, /* ḅ Ḅ */ + 0x1e07, 499, /* ḇ Ḇ */ + 0x1e09, 499, /* ḉ Ḉ */ + 0x1e0b, 499, /* ḋ Ḋ */ + 0x1e0d, 499, /* ḍ Ḍ */ + 0x1e0f, 499, /* ḏ Ḏ */ + 0x1e11, 499, /* ḑ Ḑ */ + 0x1e13, 499, /* ḓ Ḓ */ + 0x1e15, 499, /* ḕ Ḕ */ + 0x1e17, 499, /* ḗ Ḗ */ + 0x1e19, 499, /* ḙ Ḙ */ + 0x1e1b, 499, /* ḛ Ḛ */ + 0x1e1d, 499, /* ḝ Ḝ */ + 0x1e1f, 499, /* ḟ Ḟ */ + 0x1e21, 499, /* ḡ Ḡ */ + 0x1e23, 499, /* ḣ Ḣ */ + 0x1e25, 499, /* ḥ Ḥ */ + 0x1e27, 499, /* ḧ Ḧ */ + 0x1e29, 499, /* ḩ Ḩ */ + 0x1e2b, 499, /* ḫ Ḫ */ + 0x1e2d, 499, /* ḭ Ḭ */ + 0x1e2f, 499, /* ḯ Ḯ */ + 0x1e31, 499, /* ḱ Ḱ */ + 0x1e33, 499, /* ḳ Ḳ */ + 0x1e35, 499, /* ḵ Ḵ */ + 0x1e37, 499, /* ḷ Ḷ */ + 0x1e39, 499, /* ḹ Ḹ */ + 0x1e3b, 499, /* ḻ Ḻ */ + 0x1e3d, 499, /* ḽ Ḽ */ + 0x1e3f, 499, /* ḿ Ḿ */ + 0x1e41, 499, /* ṁ Ṁ */ + 0x1e43, 499, /* ṃ Ṃ */ + 0x1e45, 499, /* ṅ Ṅ */ + 0x1e47, 499, /* ṇ Ṇ */ + 0x1e49, 499, /* ṉ Ṉ */ + 0x1e4b, 499, /* ṋ Ṋ */ + 0x1e4d, 499, /* ṍ Ṍ */ + 0x1e4f, 499, /* ṏ Ṏ */ + 0x1e51, 499, /* ṑ Ṑ */ + 0x1e53, 499, /* ṓ Ṓ */ + 0x1e55, 499, /* ṕ Ṕ */ + 0x1e57, 499, /* ṗ Ṗ */ + 0x1e59, 499, /* ṙ Ṙ */ + 0x1e5b, 499, /* ṛ Ṛ */ + 0x1e5d, 499, /* ṝ Ṝ */ + 0x1e5f, 499, /* ṟ Ṟ */ + 0x1e61, 499, /* ṡ Ṡ */ + 0x1e63, 499, /* ṣ Ṣ */ + 0x1e65, 499, /* ṥ Ṥ */ + 0x1e67, 499, /* ṧ Ṧ */ + 0x1e69, 499, /* ṩ Ṩ */ + 0x1e6b, 499, /* ṫ Ṫ */ + 0x1e6d, 499, /* ṭ Ṭ */ + 0x1e6f, 499, /* ṯ Ṯ */ + 0x1e71, 499, /* ṱ Ṱ */ + 0x1e73, 499, /* ṳ Ṳ */ + 0x1e75, 499, /* ṵ Ṵ */ + 0x1e77, 499, /* ṷ Ṷ */ + 0x1e79, 499, /* ṹ Ṹ */ + 0x1e7b, 499, /* ṻ Ṻ */ + 0x1e7d, 499, /* ṽ Ṽ */ + 0x1e7f, 499, /* ṿ Ṿ */ + 0x1e81, 499, /* ẁ Ẁ */ + 0x1e83, 499, /* ẃ Ẃ */ + 0x1e85, 499, /* ẅ Ẅ */ + 0x1e87, 499, /* ẇ Ẇ */ + 0x1e89, 499, /* ẉ Ẉ */ + 0x1e8b, 499, /* ẋ Ẋ */ + 0x1e8d, 499, /* ẍ Ẍ */ + 0x1e8f, 499, /* ẏ Ẏ */ + 0x1e91, 499, /* ẑ Ẑ */ + 0x1e93, 499, /* ẓ Ẓ */ + 0x1e95, 499, /* ẕ Ẕ */ + 0x1ea1, 499, /* ạ Ạ */ + 0x1ea3, 499, /* ả Ả */ + 0x1ea5, 499, /* ấ Ấ */ + 0x1ea7, 499, /* ầ Ầ */ + 0x1ea9, 499, /* ẩ Ẩ */ + 0x1eab, 499, /* ẫ Ẫ */ + 0x1ead, 499, /* ậ Ậ */ + 0x1eaf, 499, /* ắ Ắ */ + 0x1eb1, 499, /* ằ Ằ */ + 0x1eb3, 499, /* ẳ Ẳ */ + 0x1eb5, 499, /* ẵ Ẵ */ + 0x1eb7, 499, /* ặ Ặ */ + 0x1eb9, 499, /* ẹ Ẹ */ + 0x1ebb, 499, /* ẻ Ẻ */ + 0x1ebd, 499, /* ẽ Ẽ */ + 0x1ebf, 499, /* ế Ế */ + 0x1ec1, 499, /* ề Ề */ + 0x1ec3, 499, /* ể Ể */ + 0x1ec5, 499, /* ễ Ễ */ + 0x1ec7, 499, /* ệ Ệ */ + 0x1ec9, 499, /* ỉ Ỉ */ + 0x1ecb, 499, /* ị Ị */ + 0x1ecd, 499, /* ọ Ọ */ + 0x1ecf, 499, /* ỏ Ỏ */ + 0x1ed1, 499, /* ố Ố */ + 0x1ed3, 499, /* ồ Ồ */ + 0x1ed5, 499, /* ổ Ổ */ + 0x1ed7, 499, /* ỗ Ỗ */ + 0x1ed9, 499, /* ộ Ộ */ + 0x1edb, 499, /* ớ Ớ */ + 0x1edd, 499, /* ờ Ờ */ + 0x1edf, 499, /* ở Ở */ + 0x1ee1, 499, /* ỡ Ỡ */ + 0x1ee3, 499, /* ợ Ợ */ + 0x1ee5, 499, /* ụ Ụ */ + 0x1ee7, 499, /* ủ Ủ */ + 0x1ee9, 499, /* ứ Ứ */ + 0x1eeb, 499, /* ừ Ừ */ + 0x1eed, 499, /* ử Ử */ + 0x1eef, 499, /* ữ Ữ */ + 0x1ef1, 499, /* ự Ự */ + 0x1ef3, 499, /* ỳ Ỳ */ + 0x1ef5, 499, /* ỵ Ỵ */ + 0x1ef7, 499, /* ỷ Ỷ */ + 0x1ef9, 499, /* ỹ Ỹ */ + 0x1f51, 508, /* ὑ Ὑ */ + 0x1f53, 508, /* ὓ Ὓ */ + 0x1f55, 508, /* ὕ Ὕ */ + 0x1f57, 508, /* ὗ Ὗ */ + 0x1fb3, 509, /* ᾳ ᾼ */ + 0x1fc3, 509, /* ῃ ῌ */ + 0x1fe5, 507, /* ῥ Ῥ */ + 0x1ff3, 509, /* ῳ ῼ */ +}; + +static Rune __isdigitr[] = { + 0x0030, 0x0039, + 0x0660, 0x0669, + 0x06f0, 0x06f9, + 0x07c0, 0x07c9, + 0x0966, 0x096f, + 0x09e6, 0x09ef, + 0x0a66, 0x0a6f, + 0x0ae6, 0x0aef, + 0x0b66, 0x0b6f, + 0x0be6, 0x0bef, + 0x0c66, 0x0c6f, + 0x0ce6, 0x0cef, + 0x0d66, 0x0d6f, + 0x0e50, 0x0e59, + 0x0ed0, 0x0ed9, + 0x0f20, 0x0f29, + 0x1040, 0x1049, + 0x17e0, 0x17e9, + 0x1810, 0x1819, + 0x1946, 0x194f, + 0x19d0, 0x19d9, + 0x1b50, 0x1b59, + 0xff10, 0xff19, + 0x104a0, 0x104a9, + 0x1d7ce, 0x1d7ff, +}; + +/* + * upper case ranges + * 3rd col is conversion excess 500 + */ +static +Rune _tolower2[] = +{ + 0x0041, 0x005a, 532, /* A-Z a-z */ + 0x00c0, 0x00d6, 532, /* À-Ö à-ö */ + 0x00d8, 0x00de, 532, /* Ø-Þ ø-þ */ + 0x0189, 0x018a, 705, /* Ɖ-Ɗ ɖ-ɗ */ + 0x018e, 0x018f, 702, /* Ǝ-Ə ɘ-ə */ + 0x01b1, 0x01b2, 717, /* Ʊ-Ʋ ʊ-ʋ */ + 0x0388, 0x038a, 537, /* Έ-Ί έ-ί */ + 0x038e, 0x038f, 563, /* Ύ-Ώ ύ-ώ */ + 0x0391, 0x03a1, 532, /* Α-Ρ α-ρ */ + 0x03a3, 0x03ab, 532, /* Σ-Ϋ σ-ϋ */ + 0x0401, 0x040c, 580, /* Ё-Ќ ё-ќ */ + 0x040e, 0x040f, 580, /* Ў-Џ ў-џ */ + 0x0410, 0x042f, 532, /* А-Я а-я */ + 0x0531, 0x0556, 548, /* Ա-Ֆ ա-ֆ */ + 0x10a0, 0x10c5, 548, /* Ⴀ-Ⴥ ა-ჵ */ + 0x1f08, 0x1f0f, 492, /* Ἀ-Ἇ ἀ-ἇ */ + 0x1f18, 0x1f1d, 492, /* Ἐ-Ἕ ἐ-ἕ */ + 0x1f28, 0x1f2f, 492, /* Ἠ-Ἧ ἠ-ἧ */ + 0x1f38, 0x1f3f, 492, /* Ἰ-Ἷ ἰ-ἷ */ + 0x1f48, 0x1f4d, 492, /* Ὀ-Ὅ ὀ-ὅ */ + 0x1f68, 0x1f6f, 492, /* Ὠ-Ὧ ὠ-ὧ */ + 0x1f88, 0x1f8f, 492, /* ᾈ-ᾏ ᾀ-ᾇ */ + 0x1f98, 0x1f9f, 492, /* ᾘ-ᾟ ᾐ-ᾗ */ + 0x1fa8, 0x1faf, 492, /* ᾨ-ᾯ ᾠ-ᾧ */ + 0x1fb8, 0x1fb9, 492, /* Ᾰ-Ᾱ ᾰ-ᾱ */ + 0x1fba, 0x1fbb, 426, /* Ὰ-Ά ὰ-ά */ + 0x1fc8, 0x1fcb, 414, /* Ὲ-Ή ὲ-ή */ + 0x1fd8, 0x1fd9, 492, /* Ῐ-Ῑ ῐ-ῑ */ + 0x1fda, 0x1fdb, 400, /* Ὶ-Ί ὶ-ί */ + 0x1fe8, 0x1fe9, 492, /* Ῠ-Ῡ ῠ-ῡ */ + 0x1fea, 0x1feb, 388, /* Ὺ-Ύ ὺ-ύ */ + 0x1ff8, 0x1ff9, 372, /* Ὸ-Ό ὸ-ό */ + 0x1ffa, 0x1ffb, 374, /* Ὼ-Ώ ὼ-ώ */ + 0x2160, 0x216f, 516, /* Ⅰ-Ⅿ ⅰ-ⅿ */ + 0x24b6, 0x24cf, 526, /* Ⓐ-Ⓩ ⓐ-ⓩ */ + 0xff21, 0xff3a, 532, /* A-Z a-z */ +}; + +/* + * upper case singlets + * 2nd col is conversion excess 500 + */ +static +Rune _tolower1[] = +{ + 0x0100, 501, /* Ā ā */ + 0x0102, 501, /* Ă ă */ + 0x0104, 501, /* Ą ą */ + 0x0106, 501, /* Ć ć */ + 0x0108, 501, /* Ĉ ĉ */ + 0x010a, 501, /* Ċ ċ */ + 0x010c, 501, /* Č č */ + 0x010e, 501, /* Ď ď */ + 0x0110, 501, /* Đ đ */ + 0x0112, 501, /* Ē ē */ + 0x0114, 501, /* Ĕ ĕ */ + 0x0116, 501, /* Ė ė */ + 0x0118, 501, /* Ę ę */ + 0x011a, 501, /* Ě ě */ + 0x011c, 501, /* Ĝ ĝ */ + 0x011e, 501, /* Ğ ğ */ + 0x0120, 501, /* Ġ ġ */ + 0x0122, 501, /* Ģ ģ */ + 0x0124, 501, /* Ĥ ĥ */ + 0x0126, 501, /* Ħ ħ */ + 0x0128, 501, /* Ĩ ĩ */ + 0x012a, 501, /* Ī ī */ + 0x012c, 501, /* Ĭ ĭ */ + 0x012e, 501, /* Į į */ + 0x0130, 301, /* İ i */ + 0x0132, 501, /* IJ ij */ + 0x0134, 501, /* Ĵ ĵ */ + 0x0136, 501, /* Ķ ķ */ + 0x0139, 501, /* Ĺ ĺ */ + 0x013b, 501, /* Ļ ļ */ + 0x013d, 501, /* Ľ ľ */ + 0x013f, 501, /* Ŀ ŀ */ + 0x0141, 501, /* Ł ł */ + 0x0143, 501, /* Ń ń */ + 0x0145, 501, /* Ņ ņ */ + 0x0147, 501, /* Ň ň */ + 0x014a, 501, /* Ŋ ŋ */ + 0x014c, 501, /* Ō ō */ + 0x014e, 501, /* Ŏ ŏ */ + 0x0150, 501, /* Ő ő */ + 0x0152, 501, /* Œ œ */ + 0x0154, 501, /* Ŕ ŕ */ + 0x0156, 501, /* Ŗ ŗ */ + 0x0158, 501, /* Ř ř */ + 0x015a, 501, /* Ś ś */ + 0x015c, 501, /* Ŝ ŝ */ + 0x015e, 501, /* Ş ş */ + 0x0160, 501, /* Š š */ + 0x0162, 501, /* Ţ ţ */ + 0x0164, 501, /* Ť ť */ + 0x0166, 501, /* Ŧ ŧ */ + 0x0168, 501, /* Ũ ũ */ + 0x016a, 501, /* Ū ū */ + 0x016c, 501, /* Ŭ ŭ */ + 0x016e, 501, /* Ů ů */ + 0x0170, 501, /* Ű ű */ + 0x0172, 501, /* Ų ų */ + 0x0174, 501, /* Ŵ ŵ */ + 0x0176, 501, /* Ŷ ŷ */ + 0x0178, 379, /* Ÿ ÿ */ + 0x0179, 501, /* Ź ź */ + 0x017b, 501, /* Ż ż */ + 0x017d, 501, /* Ž ž */ + 0x0181, 710, /* Ɓ ɓ */ + 0x0182, 501, /* Ƃ ƃ */ + 0x0184, 501, /* Ƅ ƅ */ + 0x0186, 706, /* Ɔ ɔ */ + 0x0187, 501, /* Ƈ ƈ */ + 0x018b, 501, /* Ƌ ƌ */ + 0x0190, 703, /* Ɛ ɛ */ + 0x0191, 501, /* Ƒ ƒ */ + 0x0193, 705, /* Ɠ ɠ */ + 0x0194, 707, /* Ɣ ɣ */ + 0x0196, 711, /* Ɩ ɩ */ + 0x0197, 709, /* Ɨ ɨ */ + 0x0198, 501, /* Ƙ ƙ */ + 0x019c, 711, /* Ɯ ɯ */ + 0x019d, 713, /* Ɲ ɲ */ + 0x01a0, 501, /* Ơ ơ */ + 0x01a2, 501, /* Ƣ ƣ */ + 0x01a4, 501, /* Ƥ ƥ */ + 0x01a7, 501, /* Ƨ ƨ */ + 0x01a9, 718, /* Ʃ ʃ */ + 0x01ac, 501, /* Ƭ ƭ */ + 0x01ae, 718, /* Ʈ ʈ */ + 0x01af, 501, /* Ư ư */ + 0x01b3, 501, /* Ƴ ƴ */ + 0x01b5, 501, /* Ƶ ƶ */ + 0x01b7, 719, /* Ʒ ʒ */ + 0x01b8, 501, /* Ƹ ƹ */ + 0x01bc, 501, /* Ƽ ƽ */ + 0x01c4, 502, /* DŽ dž */ + 0x01c5, 501, /* Dž dž */ + 0x01c7, 502, /* LJ lj */ + 0x01c8, 501, /* Lj lj */ + 0x01ca, 502, /* NJ nj */ + 0x01cb, 501, /* Nj nj */ + 0x01cd, 501, /* Ǎ ǎ */ + 0x01cf, 501, /* Ǐ ǐ */ + 0x01d1, 501, /* Ǒ ǒ */ + 0x01d3, 501, /* Ǔ ǔ */ + 0x01d5, 501, /* Ǖ ǖ */ + 0x01d7, 501, /* Ǘ ǘ */ + 0x01d9, 501, /* Ǚ ǚ */ + 0x01db, 501, /* Ǜ ǜ */ + 0x01de, 501, /* Ǟ ǟ */ + 0x01e0, 501, /* Ǡ ǡ */ + 0x01e2, 501, /* Ǣ ǣ */ + 0x01e4, 501, /* Ǥ ǥ */ + 0x01e6, 501, /* Ǧ ǧ */ + 0x01e8, 501, /* Ǩ ǩ */ + 0x01ea, 501, /* Ǫ ǫ */ + 0x01ec, 501, /* Ǭ ǭ */ + 0x01ee, 501, /* Ǯ ǯ */ + 0x01f1, 502, /* DZ dz */ + 0x01f2, 501, /* Dz dz */ + 0x01f4, 501, /* Ǵ ǵ */ + 0x01fa, 501, /* Ǻ ǻ */ + 0x01fc, 501, /* Ǽ ǽ */ + 0x01fe, 501, /* Ǿ ǿ */ + 0x0200, 501, /* Ȁ ȁ */ + 0x0202, 501, /* Ȃ ȃ */ + 0x0204, 501, /* Ȅ ȅ */ + 0x0206, 501, /* Ȇ ȇ */ + 0x0208, 501, /* Ȉ ȉ */ + 0x020a, 501, /* Ȋ ȋ */ + 0x020c, 501, /* Ȍ ȍ */ + 0x020e, 501, /* Ȏ ȏ */ + 0x0210, 501, /* Ȑ ȑ */ + 0x0212, 501, /* Ȓ ȓ */ + 0x0214, 501, /* Ȕ ȕ */ + 0x0216, 501, /* Ȗ ȗ */ + 0x0386, 538, /* Ά ά */ + 0x038c, 564, /* Ό ό */ + 0x03e2, 501, /* Ϣ ϣ */ + 0x03e4, 501, /* Ϥ ϥ */ + 0x03e6, 501, /* Ϧ ϧ */ + 0x03e8, 501, /* Ϩ ϩ */ + 0x03ea, 501, /* Ϫ ϫ */ + 0x03ec, 501, /* Ϭ ϭ */ + 0x03ee, 501, /* Ϯ ϯ */ + 0x0460, 501, /* Ѡ ѡ */ + 0x0462, 501, /* Ѣ ѣ */ + 0x0464, 501, /* Ѥ ѥ */ + 0x0466, 501, /* Ѧ ѧ */ + 0x0468, 501, /* Ѩ ѩ */ + 0x046a, 501, /* Ѫ ѫ */ + 0x046c, 501, /* Ѭ ѭ */ + 0x046e, 501, /* Ѯ ѯ */ + 0x0470, 501, /* Ѱ ѱ */ + 0x0472, 501, /* Ѳ ѳ */ + 0x0474, 501, /* Ѵ ѵ */ + 0x0476, 501, /* Ѷ ѷ */ + 0x0478, 501, /* Ѹ ѹ */ + 0x047a, 501, /* Ѻ ѻ */ + 0x047c, 501, /* Ѽ ѽ */ + 0x047e, 501, /* Ѿ ѿ */ + 0x0480, 501, /* Ҁ ҁ */ + 0x0490, 501, /* Ґ ґ */ + 0x0492, 501, /* Ғ ғ */ + 0x0494, 501, /* Ҕ ҕ */ + 0x0496, 501, /* Җ җ */ + 0x0498, 501, /* Ҙ ҙ */ + 0x049a, 501, /* Қ қ */ + 0x049c, 501, /* Ҝ ҝ */ + 0x049e, 501, /* Ҟ ҟ */ + 0x04a0, 501, /* Ҡ ҡ */ + 0x04a2, 501, /* Ң ң */ + 0x04a4, 501, /* Ҥ ҥ */ + 0x04a6, 501, /* Ҧ ҧ */ + 0x04a8, 501, /* Ҩ ҩ */ + 0x04aa, 501, /* Ҫ ҫ */ + 0x04ac, 501, /* Ҭ ҭ */ + 0x04ae, 501, /* Ү ү */ + 0x04b0, 501, /* Ұ ұ */ + 0x04b2, 501, /* Ҳ ҳ */ + 0x04b4, 501, /* Ҵ ҵ */ + 0x04b6, 501, /* Ҷ ҷ */ + 0x04b8, 501, /* Ҹ ҹ */ + 0x04ba, 501, /* Һ һ */ + 0x04bc, 501, /* Ҽ ҽ */ + 0x04be, 501, /* Ҿ ҿ */ + 0x04c1, 501, /* Ӂ ӂ */ + 0x04c3, 501, /* Ӄ ӄ */ + 0x04c7, 501, /* Ӈ ӈ */ + 0x04cb, 501, /* Ӌ ӌ */ + 0x04d0, 501, /* Ӑ ӑ */ + 0x04d2, 501, /* Ӓ ӓ */ + 0x04d4, 501, /* Ӕ ӕ */ + 0x04d6, 501, /* Ӗ ӗ */ + 0x04d8, 501, /* Ә ә */ + 0x04da, 501, /* Ӛ ӛ */ + 0x04dc, 501, /* Ӝ ӝ */ + 0x04de, 501, /* Ӟ ӟ */ + 0x04e0, 501, /* Ӡ ӡ */ + 0x04e2, 501, /* Ӣ ӣ */ + 0x04e4, 501, /* Ӥ ӥ */ + 0x04e6, 501, /* Ӧ ӧ */ + 0x04e8, 501, /* Ө ө */ + 0x04ea, 501, /* Ӫ ӫ */ + 0x04ee, 501, /* Ӯ ӯ */ + 0x04f0, 501, /* Ӱ ӱ */ + 0x04f2, 501, /* Ӳ ӳ */ + 0x04f4, 501, /* Ӵ ӵ */ + 0x04f8, 501, /* Ӹ ӹ */ + 0x1e00, 501, /* Ḁ ḁ */ + 0x1e02, 501, /* Ḃ ḃ */ + 0x1e04, 501, /* Ḅ ḅ */ + 0x1e06, 501, /* Ḇ ḇ */ + 0x1e08, 501, /* Ḉ ḉ */ + 0x1e0a, 501, /* Ḋ ḋ */ + 0x1e0c, 501, /* Ḍ ḍ */ + 0x1e0e, 501, /* Ḏ ḏ */ + 0x1e10, 501, /* Ḑ ḑ */ + 0x1e12, 501, /* Ḓ ḓ */ + 0x1e14, 501, /* Ḕ ḕ */ + 0x1e16, 501, /* Ḗ ḗ */ + 0x1e18, 501, /* Ḙ ḙ */ + 0x1e1a, 501, /* Ḛ ḛ */ + 0x1e1c, 501, /* Ḝ ḝ */ + 0x1e1e, 501, /* Ḟ ḟ */ + 0x1e20, 501, /* Ḡ ḡ */ + 0x1e22, 501, /* Ḣ ḣ */ + 0x1e24, 501, /* Ḥ ḥ */ + 0x1e26, 501, /* Ḧ ḧ */ + 0x1e28, 501, /* Ḩ ḩ */ + 0x1e2a, 501, /* Ḫ ḫ */ + 0x1e2c, 501, /* Ḭ ḭ */ + 0x1e2e, 501, /* Ḯ ḯ */ + 0x1e30, 501, /* Ḱ ḱ */ + 0x1e32, 501, /* Ḳ ḳ */ + 0x1e34, 501, /* Ḵ ḵ */ + 0x1e36, 501, /* Ḷ ḷ */ + 0x1e38, 501, /* Ḹ ḹ */ + 0x1e3a, 501, /* Ḻ ḻ */ + 0x1e3c, 501, /* Ḽ ḽ */ + 0x1e3e, 501, /* Ḿ ḿ */ + 0x1e40, 501, /* Ṁ ṁ */ + 0x1e42, 501, /* Ṃ ṃ */ + 0x1e44, 501, /* Ṅ ṅ */ + 0x1e46, 501, /* Ṇ ṇ */ + 0x1e48, 501, /* Ṉ ṉ */ + 0x1e4a, 501, /* Ṋ ṋ */ + 0x1e4c, 501, /* Ṍ ṍ */ + 0x1e4e, 501, /* Ṏ ṏ */ + 0x1e50, 501, /* Ṑ ṑ */ + 0x1e52, 501, /* Ṓ ṓ */ + 0x1e54, 501, /* Ṕ ṕ */ + 0x1e56, 501, /* Ṗ ṗ */ + 0x1e58, 501, /* Ṙ ṙ */ + 0x1e5a, 501, /* Ṛ ṛ */ + 0x1e5c, 501, /* Ṝ ṝ */ + 0x1e5e, 501, /* Ṟ ṟ */ + 0x1e60, 501, /* Ṡ ṡ */ + 0x1e62, 501, /* Ṣ ṣ */ + 0x1e64, 501, /* Ṥ ṥ */ + 0x1e66, 501, /* Ṧ ṧ */ + 0x1e68, 501, /* Ṩ ṩ */ + 0x1e6a, 501, /* Ṫ ṫ */ + 0x1e6c, 501, /* Ṭ ṭ */ + 0x1e6e, 501, /* Ṯ ṯ */ + 0x1e70, 501, /* Ṱ ṱ */ + 0x1e72, 501, /* Ṳ ṳ */ + 0x1e74, 501, /* Ṵ ṵ */ + 0x1e76, 501, /* Ṷ ṷ */ + 0x1e78, 501, /* Ṹ ṹ */ + 0x1e7a, 501, /* Ṻ ṻ */ + 0x1e7c, 501, /* Ṽ ṽ */ + 0x1e7e, 501, /* Ṿ ṿ */ + 0x1e80, 501, /* Ẁ ẁ */ + 0x1e82, 501, /* Ẃ ẃ */ + 0x1e84, 501, /* Ẅ ẅ */ + 0x1e86, 501, /* Ẇ ẇ */ + 0x1e88, 501, /* Ẉ ẉ */ + 0x1e8a, 501, /* Ẋ ẋ */ + 0x1e8c, 501, /* Ẍ ẍ */ + 0x1e8e, 501, /* Ẏ ẏ */ + 0x1e90, 501, /* Ẑ ẑ */ + 0x1e92, 501, /* Ẓ ẓ */ + 0x1e94, 501, /* Ẕ ẕ */ + 0x1ea0, 501, /* Ạ ạ */ + 0x1ea2, 501, /* Ả ả */ + 0x1ea4, 501, /* Ấ ấ */ + 0x1ea6, 501, /* Ầ ầ */ + 0x1ea8, 501, /* Ẩ ẩ */ + 0x1eaa, 501, /* Ẫ ẫ */ + 0x1eac, 501, /* Ậ ậ */ + 0x1eae, 501, /* Ắ ắ */ + 0x1eb0, 501, /* Ằ ằ */ + 0x1eb2, 501, /* Ẳ ẳ */ + 0x1eb4, 501, /* Ẵ ẵ */ + 0x1eb6, 501, /* Ặ ặ */ + 0x1eb8, 501, /* Ẹ ẹ */ + 0x1eba, 501, /* Ẻ ẻ */ + 0x1ebc, 501, /* Ẽ ẽ */ + 0x1ebe, 501, /* Ế ế */ + 0x1ec0, 501, /* Ề ề */ + 0x1ec2, 501, /* Ể ể */ + 0x1ec4, 501, /* Ễ ễ */ + 0x1ec6, 501, /* Ệ ệ */ + 0x1ec8, 501, /* Ỉ ỉ */ + 0x1eca, 501, /* Ị ị */ + 0x1ecc, 501, /* Ọ ọ */ + 0x1ece, 501, /* Ỏ ỏ */ + 0x1ed0, 501, /* Ố ố */ + 0x1ed2, 501, /* Ồ ồ */ + 0x1ed4, 501, /* Ổ ổ */ + 0x1ed6, 501, /* Ỗ ỗ */ + 0x1ed8, 501, /* Ộ ộ */ + 0x1eda, 501, /* Ớ ớ */ + 0x1edc, 501, /* Ờ ờ */ + 0x1ede, 501, /* Ở ở */ + 0x1ee0, 501, /* Ỡ ỡ */ + 0x1ee2, 501, /* Ợ ợ */ + 0x1ee4, 501, /* Ụ ụ */ + 0x1ee6, 501, /* Ủ ủ */ + 0x1ee8, 501, /* Ứ ứ */ + 0x1eea, 501, /* Ừ ừ */ + 0x1eec, 501, /* Ử ử */ + 0x1eee, 501, /* Ữ ữ */ + 0x1ef0, 501, /* Ự ự */ + 0x1ef2, 501, /* Ỳ ỳ */ + 0x1ef4, 501, /* Ỵ ỵ */ + 0x1ef6, 501, /* Ỷ ỷ */ + 0x1ef8, 501, /* Ỹ ỹ */ + 0x1f59, 492, /* Ὑ ὑ */ + 0x1f5b, 492, /* Ὓ ὓ */ + 0x1f5d, 492, /* Ὕ ὕ */ + 0x1f5f, 492, /* Ὗ ὗ */ + 0x1fbc, 491, /* ᾼ ᾳ */ + 0x1fcc, 491, /* ῌ ῃ */ + 0x1fec, 493, /* Ῥ ῥ */ + 0x1ffc, 491, /* ῼ ῳ */ +}; + +/* + * title characters are those between + * upper and lower case. ie DZ Dz dz + */ +static +Rune _totitle1[] = +{ + 0x01c4, 501, /* DŽ Dž */ + 0x01c6, 499, /* dž Dž */ + 0x01c7, 501, /* LJ Lj */ + 0x01c9, 499, /* lj Lj */ + 0x01ca, 501, /* NJ Nj */ + 0x01cc, 499, /* nj Nj */ + 0x01f1, 501, /* DZ Dz */ + 0x01f3, 499, /* dz Dz */ +}; + +static +Rune* +bsearch(Rune c, Rune *t, int n, int ne) +{ + Rune *p; + int m; + + while(n > 1) { + m = n/2; + p = t + m*ne; + if(c >= p[0]) { + t = p; + n = n-m; + } else + n = m; + } + if(n && c >= t[0]) + return t; + return 0; +} + +Rune +tolowerrune(Rune c) +{ + Rune *p; + + p = bsearch(c, _tolower2, nelem(_tolower2)/3, 3); + if(p && c >= p[0] && c <= p[1]) + return c + p[2] - 500; + p = bsearch(c, _tolower1, nelem(_tolower1)/2, 2); + if(p && c == p[0]) + return c + p[1] - 500; + return c; +} + +Rune +toupperrune(Rune c) +{ + Rune *p; + + p = bsearch(c, _toupper2, nelem(_toupper2)/3, 3); + if(p && c >= p[0] && c <= p[1]) + return c + p[2] - 500; + p = bsearch(c, _toupper1, nelem(_toupper1)/2, 2); + if(p && c == p[0]) + return c + p[1] - 500; + return c; +} + +Rune +totitlerune(Rune c) +{ + Rune *p; + + p = bsearch(c, _totitle1, nelem(_totitle1)/2, 2); + if(p && c == p[0]) + return c + p[1] - 500; + return c; +} + +int +islowerrune(Rune c) +{ + Rune *p; + + p = bsearch(c, _toupper2, nelem(_toupper2)/3, 3); + if(p && c >= p[0] && c <= p[1]) + return 1; + p = bsearch(c, _toupper1, nelem(_toupper1)/2, 2); + if(p && c == p[0]) + return 1; + return 0; +} + +int +isupperrune(Rune c) +{ + Rune *p; + + p = bsearch(c, _tolower2, nelem(_tolower2)/3, 3); + if(p && c >= p[0] && c <= p[1]) + return 1; + p = bsearch(c, _tolower1, nelem(_tolower1)/2, 2); + if(p && c == p[0]) + return 1; + return 0; +} + +int +isalpharune(Rune c) +{ + Rune *p; + + if(isupperrune(c) || islowerrune(c)) + return 1; + p = bsearch(c, _alpha2, nelem(_alpha2)/2, 2); + if(p && c >= p[0] && c <= p[1]) + return 1; + p = bsearch(c, _alpha1, nelem(_alpha1), 1); + if(p && c == p[0]) + return 1; + return 0; +} + +int +istitlerune(Rune c) +{ + return isupperrune(c) && islowerrune(c); +} + +int +isspacerune(Rune c) +{ + Rune *p; + + p = bsearch(c, _space2, nelem(_space2)/2, 2); + if(p && c >= p[0] && c <= p[1]) + return 1; + return 0; +} + +int +isdigitrune(Rune c) +{ + Rune *p; + + p = bsearch(c, __isdigitr, nelem(__isdigitr)/2, 2); + if(p && c >= p[0] && c <= p[1]) + return 1; + return 0; +} diff --git a/sys/src/libc/port/sin.c b/sys/src/libc/port/sin.c new file mode 100755 index 000000000..7072dd406 --- /dev/null +++ b/sys/src/libc/port/sin.c @@ -0,0 +1,68 @@ +/* + C program for floating point sin/cos. + Calls modf. + There are no error exits. + Coefficients are #3370 from Hart & Cheney (18.80D). +*/ + +#include <u.h> +#include <libc.h> + +#define p0 .1357884097877375669092680e8 +#define p1 -.4942908100902844161158627e7 +#define p2 .4401030535375266501944918e6 +#define p3 -.1384727249982452873054457e5 +#define p4 .1459688406665768722226959e3 +#define q0 .8644558652922534429915149e7 +#define q1 .4081792252343299749395779e6 +#define q2 .9463096101538208180571257e4 +#define q3 .1326534908786136358911494e3 + +static +double +sinus(double arg, int quad) +{ + double e, f, ysq, x, y, temp1, temp2; + int k; + + x = arg; + if(x < 0) { + x = -x; + quad += 2; + } + x *= 1/PIO2; /* underflow? */ + if(x > 32764) { + y = modf(x, &e); + e += quad; + modf(0.25*e, &f); + quad = e - 4*f; + } else { + k = x; + y = x - k; + quad += k; + quad &= 3; + } + if(quad & 1) + y = 1-y; + if(quad > 1) + y = -y; + + ysq = y*y; + temp1 = ((((p4*ysq+p3)*ysq+p2)*ysq+p1)*ysq+p0)*y; + temp2 = ((((ysq+q3)*ysq+q2)*ysq+q1)*ysq+q0); + return temp1/temp2; +} + +double +cos(double arg) +{ + if(arg < 0) + arg = -arg; + return sinus(arg, 1); +} + +double +sin(double arg) +{ + return sinus(arg, 0); +} diff --git a/sys/src/libc/port/sinh.c b/sys/src/libc/port/sinh.c new file mode 100755 index 000000000..115d42c0e --- /dev/null +++ b/sys/src/libc/port/sinh.c @@ -0,0 +1,62 @@ +#include <u.h> +#include <libc.h> + +/* + * sinh(arg) returns the hyperbolic sine of its floating- + * point argument. + * + * The exponential function is called for arguments + * greater in magnitude than 0.5. + * + * A series is used for arguments smaller in magnitude than 0.5. + * The coefficients are #2029 from Hart & Cheney. (20.36D) + * + * cosh(arg) is computed from the exponential function for + * all arguments. + */ + +static double p0 = -0.6307673640497716991184787251e+6; +static double p1 = -0.8991272022039509355398013511e+5; +static double p2 = -0.2894211355989563807284660366e+4; +static double p3 = -0.2630563213397497062819489e+2; +static double q0 = -0.6307673640497716991212077277e+6; +static double q1 = 0.1521517378790019070696485176e+5; +static double q2 = -0.173678953558233699533450911e+3; + +double +sinh(double arg) +{ + double temp, argsq; + int sign; + + sign = 0; + if(arg < 0) { + arg = -arg; + sign++; + } + if(arg > 21) { + temp = exp(arg)/2; + goto out; + } + if(arg > 0.5) { + temp = (exp(arg) - exp(-arg))/2; + goto out; + } + argsq = arg*arg; + temp = (((p3*argsq+p2)*argsq+p1)*argsq+p0)*arg; + temp /= (((argsq+q2)*argsq+q1)*argsq+q0); +out: + if(sign) + temp = -temp; + return temp; +} + +double +cosh(double arg) +{ + if(arg < 0) + arg = - arg; + if(arg > 21) + return exp(arg)/2; + return (exp(arg) + exp(-arg))/2; +} diff --git a/sys/src/libc/port/sqrt.c b/sys/src/libc/port/sqrt.c new file mode 100755 index 000000000..a92efac88 --- /dev/null +++ b/sys/src/libc/port/sqrt.c @@ -0,0 +1,54 @@ +/* + sqrt returns the square root of its floating + point argument. Newton's method. + + calls frexp +*/ + +#include <u.h> +#include <libc.h> + +double +sqrt(double arg) +{ + double x, temp; + int exp, i; + + if(arg <= 0) { + if(arg < 0) + return NaN(); + return 0; + } + if(isInf(arg, 1)) + return arg; + x = frexp(arg, &exp); + while(x < 0.5) { + x *= 2; + exp--; + } + /* + * NOTE + * this wont work on 1's comp + */ + if(exp & 1) { + x *= 2; + exp--; + } + temp = 0.5 * (1.0+x); + + while(exp > 60) { + temp *= (1L<<30); + exp -= 60; + } + while(exp < -60) { + temp /= (1L<<30); + exp += 60; + } + if(exp >= 0) + temp *= 1L << (exp/2); + else + temp /= 1L << (-exp/2); + for(i=0; i<=4; i++) + temp = 0.5*(temp + arg/temp); + return temp; +} diff --git a/sys/src/libc/port/strcat.c b/sys/src/libc/port/strcat.c new file mode 100755 index 000000000..137dc8195 --- /dev/null +++ b/sys/src/libc/port/strcat.c @@ -0,0 +1,10 @@ +#include <u.h> +#include <libc.h> + +char* +strcat(char *s1, char *s2) +{ + + strcpy(strchr(s1, 0), s2); + return s1; +} diff --git a/sys/src/libc/port/strchr.c b/sys/src/libc/port/strchr.c new file mode 100755 index 000000000..1e9aab597 --- /dev/null +++ b/sys/src/libc/port/strchr.c @@ -0,0 +1,20 @@ +#include <u.h> +#include <libc.h> + +char* +strchr(char *s, int c) +{ + char c0 = c; + char c1; + + if(c == 0) { + while(*s++) + ; + return s-1; + } + + while(c1 = *s++) + if(c1 == c0) + return s-1; + return 0; +} diff --git a/sys/src/libc/port/strcmp.c b/sys/src/libc/port/strcmp.c new file mode 100755 index 000000000..9d0c0b398 --- /dev/null +++ b/sys/src/libc/port/strcmp.c @@ -0,0 +1,20 @@ +#include <u.h> +#include <libc.h> + +int +strcmp(char *s1, char *s2) +{ + unsigned c1, c2; + + for(;;) { + c1 = *s1++; + c2 = *s2++; + if(c1 != c2) { + if(c1 > c2) + return 1; + return -1; + } + if(c1 == 0) + return 0; + } +} diff --git a/sys/src/libc/port/strcpy.c b/sys/src/libc/port/strcpy.c new file mode 100755 index 000000000..233a9c1b0 --- /dev/null +++ b/sys/src/libc/port/strcpy.c @@ -0,0 +1,16 @@ +#include <u.h> +#include <libc.h> +#define N 10000 + +char* +strcpy(char *s1, char *s2) +{ + char *os1; + + os1 = s1; + while(!memccpy(s1, s2, 0, N)) { + s1 += N; + s2 += N; + } + return os1; +} diff --git a/sys/src/libc/port/strcspn.c b/sys/src/libc/port/strcspn.c new file mode 100755 index 000000000..8349af335 --- /dev/null +++ b/sys/src/libc/port/strcspn.c @@ -0,0 +1,21 @@ +#include <u.h> +#include <libc.h> + +#define N 256 + +long +strcspn(char *s, char *b) +{ + char map[N], *os; + + memset(map, 0, N); + for(;;) { + map[*(uchar*)b] = 1; + if(*b++ == 0) + break; + } + os = s; + while(map[*(uchar*)s++] == 0) + ; + return s - os - 1; +} diff --git a/sys/src/libc/port/strdup.c b/sys/src/libc/port/strdup.c new file mode 100755 index 000000000..3d5fe523f --- /dev/null +++ b/sys/src/libc/port/strdup.c @@ -0,0 +1,14 @@ +#include <u.h> +#include <libc.h> + +char* +strdup(char *s) +{ + char *ns; + + ns = malloc(strlen(s) + 1); + if(ns == 0) + return 0; + + return strcpy(ns, s); +} diff --git a/sys/src/libc/port/strecpy.c b/sys/src/libc/port/strecpy.c new file mode 100755 index 000000000..a44dffdd8 --- /dev/null +++ b/sys/src/libc/port/strecpy.c @@ -0,0 +1,17 @@ +#include <u.h> +#include <libc.h> + +char* +strecpy(char *to, char *e, char *from) +{ + if(to >= e) + return to; + to = memccpy(to, from, '\0', e - to); + if(to == nil){ + to = e - 1; + *to = '\0'; + }else{ + to--; + } + return to; +} diff --git a/sys/src/libc/port/strlen.c b/sys/src/libc/port/strlen.c new file mode 100755 index 000000000..9a3c372a5 --- /dev/null +++ b/sys/src/libc/port/strlen.c @@ -0,0 +1,9 @@ +#include <u.h> +#include <libc.h> + +long +strlen(char *s) +{ + + return strchr(s, 0) - s; +} diff --git a/sys/src/libc/port/strncat.c b/sys/src/libc/port/strncat.c new file mode 100755 index 000000000..9d793e42d --- /dev/null +++ b/sys/src/libc/port/strncat.c @@ -0,0 +1,19 @@ +#include <u.h> +#include <libc.h> + +char* +strncat(char *s1, char *s2, long n) +{ + char *os1; + + os1 = s1; + while(*s1++) + ; + s1--; + while(*s1++ = *s2++) + if(--n < 0) { + s1[-1] = 0; + break; + } + return os1; +} diff --git a/sys/src/libc/port/strncmp.c b/sys/src/libc/port/strncmp.c new file mode 100755 index 000000000..b61db6d5d --- /dev/null +++ b/sys/src/libc/port/strncmp.c @@ -0,0 +1,22 @@ +#include <u.h> +#include <libc.h> + +int +strncmp(char *s1, char *s2, long n) +{ + unsigned c1, c2; + + while(n > 0) { + c1 = *s1++; + c2 = *s2++; + n--; + if(c1 != c2) { + if(c1 > c2) + return 1; + return -1; + } + if(c1 == 0) + break; + } + return 0; +} diff --git a/sys/src/libc/port/strncpy.c b/sys/src/libc/port/strncpy.c new file mode 100755 index 000000000..bd5acdedb --- /dev/null +++ b/sys/src/libc/port/strncpy.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> + +char* +strncpy(char *s1, char *s2, long n) +{ + int i; + char *os1; + + os1 = s1; + for(i = 0; i < n; i++) + if((*s1++ = *s2++) == 0) { + while(++i < n) + *s1++ = 0; + return os1; + } + return os1; +} diff --git a/sys/src/libc/port/strpbrk.c b/sys/src/libc/port/strpbrk.c new file mode 100755 index 000000000..bbd91eafb --- /dev/null +++ b/sys/src/libc/port/strpbrk.c @@ -0,0 +1,22 @@ +#include <u.h> +#include <libc.h> +#define N 256 + +char* +strpbrk(char *cs, char *cb) +{ + char map[N]; + uchar *s=(uchar*)cs, *b=(uchar*)cb; + + memset(map, 0, N); + for(;;) { + map[*b] = 1; + if(*b++ == 0) + break; + } + while(map[*s++] == 0) + ; + if(*--s) + return (char*)s; + return 0; +} diff --git a/sys/src/libc/port/strrchr.c b/sys/src/libc/port/strrchr.c new file mode 100755 index 000000000..18fd38634 --- /dev/null +++ b/sys/src/libc/port/strrchr.c @@ -0,0 +1,15 @@ +#include <u.h> +#include <libc.h> + +char* +strrchr(char *s, int c) +{ + char *r; + + if(c == 0) + return strchr(s, 0); + r = 0; + while(s = strchr(s, c)) + r = s++; + return r; +} diff --git a/sys/src/libc/port/strspn.c b/sys/src/libc/port/strspn.c new file mode 100755 index 000000000..8744fd0ec --- /dev/null +++ b/sys/src/libc/port/strspn.c @@ -0,0 +1,18 @@ +#include <u.h> +#include <libc.h> + +#define N 256 + +long +strspn(char *s, char *b) +{ + char map[N], *os; + + memset(map, 0, N); + while(*b) + map[*(uchar *)b++] = 1; + os = s; + while(map[*(uchar *)s++]) + ; + return s - os - 1; +} diff --git a/sys/src/libc/port/strstr.c b/sys/src/libc/port/strstr.c new file mode 100755 index 000000000..4541ccd04 --- /dev/null +++ b/sys/src/libc/port/strstr.c @@ -0,0 +1,29 @@ +#include <u.h> +#include <libc.h> + +/* + * Return pointer to first occurrence of s2 in s1, + * 0 if none + */ +char* +strstr(char *s1, char *s2) +{ + char *p, *pa, *pb; + int c0, c; + + c0 = *s2; + if(c0 == 0) + return s1; + s2++; + for(p=strchr(s1, c0); p; p=strchr(p+1, c0)) { + pa = p; + for(pb=s2;; pb++) { + c = *pb; + if(c == 0) + return p; + if(c != *++pa) + break; + } + } + return 0; +} diff --git a/sys/src/libc/port/strtod.c b/sys/src/libc/port/strtod.c new file mode 100755 index 000000000..9ea252856 --- /dev/null +++ b/sys/src/libc/port/strtod.c @@ -0,0 +1,520 @@ +#include <u.h> +#include <libc.h> +#include <ctype.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, + Fsign = 1<<0, // found - + Fesign = 1<<1, // found e- + Fdpoint = 1<<2, // found . + + 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 +}; + +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); + +typedef struct Tab Tab; +struct Tab +{ + int bp; + int siz; + char* cmp; +}; + +double +strtod(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=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 = 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 */ + 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); + } + d = 0; + for(i=0; i<Prec; i++) + d = d*One + mid[i]; + if(flag & Fsign) + d = -d; + d = ldexp(d, bp - Prec*Nbits); + return d; + +ret0: + return 0; + +retnan: + return NaN(); + +retinf: + if(flag & Fsign) + return Inf(-1); + return Inf(+1); +} + +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 >= nelem(tab1)) + d = 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 >= nelem(tab2)) + d = 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; +} diff --git a/sys/src/libc/port/strtok.c b/sys/src/libc/port/strtok.c new file mode 100755 index 000000000..cb8d5fdf5 --- /dev/null +++ b/sys/src/libc/port/strtok.c @@ -0,0 +1,30 @@ +#include <u.h> +#include <libc.h> + +#define N 256 + +char* +strtok(char *s, char *b) +{ + static char *under_rock; + char map[N], *os; + + memset(map, 0, N); + while(*b) + map[*(uchar*)b++] = 1; + if(s == 0) + s = under_rock; + while(map[*(uchar*)s++]) + ; + if(*--s == 0) + return 0; + os = s; + while(map[*(uchar*)s] == 0) + if(*s++ == 0) { + under_rock = s-1; + return os; + } + *s++ = 0; + under_rock = s; + return os; +} diff --git a/sys/src/libc/port/strtol.c b/sys/src/libc/port/strtol.c new file mode 100755 index 000000000..e512910a8 --- /dev/null +++ b/sys/src/libc/port/strtol.c @@ -0,0 +1,101 @@ +#include <u.h> +#include <libc.h> + +#define LONG_MAX 2147483647L +#define LONG_MIN -2147483648L + +long +strtol(char *nptr, char **endptr, int base) +{ + char *p; + long n, nn, m; + int c, ovfl, v, neg, ndig; + + p = nptr; + neg = 0; + n = 0; + ndig = 0; + ovfl = 0; + + /* + * White space + */ + for(;; p++) { + switch(*p) { + case ' ': + case '\t': + case '\n': + case '\f': + case '\r': + case '\v': + continue; + } + break; + } + + /* + * Sign + */ + if(*p=='-' || *p=='+') + if(*p++ == '-') + neg = 1; + + /* + * Base + */ + if(base==0) { + base = 10; + if(*p == '0') { + base = 8; + if(p[1]=='x' || p[1]=='X') { + p += 2; + base = 16; + } + } + } else + if(base==16 && *p=='0'){ + if(p[1]=='x' || p[1]=='X') + p += 2; + } else + if(base<0 || 36<base) + goto Return; + + /* + * Non-empty sequence of digits + */ + m = LONG_MAX/base; + for(;; p++,ndig++){ + c = *p; + v = base; + if('0'<=c && c<='9') + v = c - '0'; + else + if('a'<=c && c<='z') + v = c - 'a' + 10; + else + if('A'<=c && c<='Z') + v = c - 'A' + 10; + if(v >= base) + break; + if(n > m) + ovfl = 1; + nn = n*base + v; + if(nn < n) + ovfl = 1; + n = nn; + } + +Return: + if(ndig == 0) + p = nptr; + if(endptr) + *endptr = p; + if(ovfl){ + if(neg) + return LONG_MIN; + return LONG_MAX; + } + if(neg) + return -n; + return n; +} diff --git a/sys/src/libc/port/strtoll.c b/sys/src/libc/port/strtoll.c new file mode 100755 index 000000000..444728ae5 --- /dev/null +++ b/sys/src/libc/port/strtoll.c @@ -0,0 +1,101 @@ +#include <u.h> +#include <libc.h> + +#define VLONG_MAX ~(1LL<<63) +#define VLONG_MIN (1LL<<63) + +vlong +strtoll(char *nptr, char **endptr, int base) +{ + char *p; + vlong n, nn, m; + int c, ovfl, v, neg, ndig; + + p = nptr; + neg = 0; + n = 0; + ndig = 0; + ovfl = 0; + + /* + * White space + */ + for(;; p++) { + switch(*p) { + case ' ': + case '\t': + case '\n': + case '\f': + case '\r': + case '\v': + continue; + } + break; + } + + /* + * Sign + */ + if(*p=='-' || *p=='+') + if(*p++ == '-') + neg = 1; + + /* + * Base + */ + if(base==0){ + base = 10; + if(*p == '0') { + base = 8; + if(p[1]=='x' || p[1]=='X') { + p += 2; + base = 16; + } + } + } else + if(base==16 && *p=='0') { + if(p[1]=='x' || p[1]=='X') + p += 2; + } else + if(base<0 || 36<base) + goto Return; + + /* + * Non-empty sequence of digits + */ + m = VLONG_MAX/base; + for(;; p++,ndig++) { + c = *p; + v = base; + if('0'<=c && c<='9') + v = c - '0'; + else + if('a'<=c && c<='z') + v = c - 'a' + 10; + else + if('A'<=c && c<='Z') + v = c - 'A' + 10; + if(v >= base) + break; + if(n > m) + ovfl = 1; + nn = n*base + v; + if(nn < n) + ovfl = 1; + n = nn; + } + +Return: + if(ndig == 0) + p = nptr; + if(endptr) + *endptr = p; + if(ovfl){ + if(neg) + return VLONG_MIN; + return VLONG_MAX; + } + if(neg) + return -n; + return n; +} diff --git a/sys/src/libc/port/strtoul.c b/sys/src/libc/port/strtoul.c new file mode 100755 index 000000000..6a12fdd94 --- /dev/null +++ b/sys/src/libc/port/strtoul.c @@ -0,0 +1,97 @@ +#include <u.h> +#include <libc.h> + +#define ULONG_MAX 4294967295UL + +ulong +strtoul(char *nptr, char **endptr, int base) +{ + char *p; + ulong n, nn, m; + int c, ovfl, neg, v, ndig; + + p = nptr; + neg = 0; + n = 0; + ndig = 0; + ovfl = 0; + + /* + * White space + */ + for(;;p++){ + switch(*p){ + case ' ': + case '\t': + case '\n': + case '\f': + case '\r': + case '\v': + continue; + } + break; + } + + /* + * Sign + */ + if(*p=='-' || *p=='+') + if(*p++ == '-') + neg = 1; + + /* + * Base + */ + if(base==0){ + if(*p != '0') + base = 10; + else{ + base = 8; + if(p[1]=='x' || p[1]=='X') + base = 16; + } + } + if(base<2 || 36<base) + goto Return; + if(base==16 && *p=='0'){ + if(p[1]=='x' || p[1]=='X') + if(('0' <= p[2] && p[2] <= '9') + ||('a' <= p[2] && p[2] <= 'f') + ||('A' <= p[2] && p[2] <= 'F')) + p += 2; + } + /* + * Non-empty sequence of digits + */ + n = 0; + m = ULONG_MAX/base; + for(;; p++,ndig++){ + c = *p; + v = base; + if('0'<=c && c<='9') + v = c - '0'; + else if('a'<=c && c<='z') + v = c - 'a' + 10; + else if('A'<=c && c<='Z') + v = c - 'A' + 10; + if(v >= base) + break; + if(n > m) + ovfl = 1; + nn = n*base + v; + if(nn < n) + ovfl = 1; + n = nn; + } + + Return: + if(ndig == 0) + p = nptr; + if(endptr) + *endptr = p; + if(ovfl) + return ULONG_MAX; + if(neg) + return -n; + return n; +} diff --git a/sys/src/libc/port/strtoull.c b/sys/src/libc/port/strtoull.c new file mode 100755 index 000000000..85ab7c5fc --- /dev/null +++ b/sys/src/libc/port/strtoull.c @@ -0,0 +1,97 @@ +#include <u.h> +#include <libc.h> + +#define UVLONG_MAX (1LL<<63) + +uvlong +strtoull(char *nptr, char **endptr, int base) +{ + char *p; + uvlong n, nn, m; + int c, ovfl, v, neg, ndig; + + p = nptr; + neg = 0; + n = 0; + ndig = 0; + ovfl = 0; + + /* + * White space + */ + for(;; p++) { + switch(*p) { + case ' ': + case '\t': + case '\n': + case '\f': + case '\r': + case '\v': + continue; + } + break; + } + + /* + * Sign + */ + if(*p == '-' || *p == '+') + if(*p++ == '-') + neg = 1; + + /* + * Base + */ + if(base == 0) { + base = 10; + if(*p == '0') { + base = 8; + if(p[1] == 'x' || p[1] == 'X'){ + p += 2; + base = 16; + } + } + } else + if(base == 16 && *p == '0') { + if(p[1] == 'x' || p[1] == 'X') + p += 2; + } else + if(base < 0 || 36 < base) + goto Return; + + /* + * Non-empty sequence of digits + */ + m = UVLONG_MAX/base; + for(;; p++,ndig++) { + c = *p; + v = base; + if('0' <= c && c <= '9') + v = c - '0'; + else + if('a' <= c && c <= 'z') + v = c - 'a' + 10; + else + if('A' <= c && c <= 'Z') + v = c - 'A' + 10; + if(v >= base) + break; + if(n > m) + ovfl = 1; + nn = n*base + v; + if(nn < n) + ovfl = 1; + n = nn; + } + +Return: + if(ndig == 0) + p = nptr; + if(endptr) + *endptr = p; + if(ovfl) + return UVLONG_MAX; + if(neg) + return -n; + return n; +} diff --git a/sys/src/libc/port/tan.c b/sys/src/libc/port/tan.c new file mode 100755 index 000000000..b562e282d --- /dev/null +++ b/sys/src/libc/port/tan.c @@ -0,0 +1,67 @@ +/* + floating point tangent + + A series is used after range reduction. + Coefficients are #4285 from Hart & Cheney. (19.74D) + */ + +#include <u.h> +#include <libc.h> + +static double p0 = -0.1306820264754825668269611177e+5; +static double p1 = 0.1055970901714953193602353981e+4; +static double p2 = -0.1550685653483266376941705728e+2; +static double p3 = 0.3422554387241003435328470489e-1; +static double p4 = 0.3386638642677172096076369e-4; +static double q0 = -0.1663895238947119001851464661e+5; +static double q1 = 0.4765751362916483698926655581e+4; +static double q2 = -0.1555033164031709966900124574e+3; + +double +tan(double arg) +{ + double temp, e, x, xsq; + int flag, sign, i; + + flag = 0; + sign = 0; + if(arg < 0){ + arg = -arg; + sign++; + } + arg = 2*arg/PIO2; /* overflow? */ + x = modf(arg, &e); + i = e; + switch(i%4) { + case 1: + x = 1 - x; + flag = 1; + break; + + case 2: + sign = !sign; + flag = 1; + break; + + case 3: + x = 1 - x; + sign = !sign; + break; + + case 0: + break; + } + + xsq = x*x; + temp = ((((p4*xsq+p3)*xsq+p2)*xsq+p1)*xsq+p0)*x; + temp = temp/(((xsq+q2)*xsq+q1)*xsq+q0); + + if(flag) { + if(temp == 0) + return NaN(); + temp = 1/temp; + } + if(sign) + temp = -temp; + return temp; +} diff --git a/sys/src/libc/port/tanh.c b/sys/src/libc/port/tanh.c new file mode 100755 index 000000000..32e3a35ac --- /dev/null +++ b/sys/src/libc/port/tanh.c @@ -0,0 +1,25 @@ +#include <u.h> +#include <libc.h> + +/* + tanh(arg) computes the hyperbolic tangent of its floating + point argument. + + sinh and cosh are called except for large arguments, which + would cause overflow improperly. + */ + +double +tanh(double arg) +{ + + if(arg < 0) { + arg = -arg; + if(arg > 21) + return -1; + return -sinh(arg)/cosh(arg); + } + if(arg > 21) + return 1; + return sinh(arg)/cosh(arg); +} diff --git a/sys/src/libc/port/tokenize.c b/sys/src/libc/port/tokenize.c new file mode 100755 index 000000000..de234d440 --- /dev/null +++ b/sys/src/libc/port/tokenize.c @@ -0,0 +1,107 @@ +#include <u.h> +#include <libc.h> + +static char qsep[] = " \t\r\n"; + +static char* +qtoken(char *s, char *sep) +{ + int quoting; + char *t; + + quoting = 0; + t = s; /* s is output string, t is input string */ + while(*t!='\0' && (quoting || utfrune(sep, *t)==nil)){ + if(*t != '\''){ + *s++ = *t++; + continue; + } + /* *t is a quote */ + if(!quoting){ + quoting = 1; + t++; + continue; + } + /* quoting and we're on a quote */ + if(t[1] != '\''){ + /* end of quoted section; absorb closing quote */ + t++; + quoting = 0; + continue; + } + /* doubled quote; fold one quote into two */ + t++; + *s++ = *t++; + } + if(*s != '\0'){ + *s = '\0'; + if(t == s) + t++; + } + return t; +} + +static char* +etoken(char *t, char *sep) +{ + int quoting; + + /* move to end of next token */ + quoting = 0; + while(*t!='\0' && (quoting || utfrune(sep, *t)==nil)){ + if(*t != '\''){ + t++; + continue; + } + /* *t is a quote */ + if(!quoting){ + quoting = 1; + t++; + continue; + } + /* quoting and we're on a quote */ + if(t[1] != '\''){ + /* end of quoted section; absorb closing quote */ + t++; + quoting = 0; + continue; + } + /* doubled quote; fold one quote into two */ + t += 2; + } + return t; +} + +int +gettokens(char *s, char **args, int maxargs, char *sep) +{ + int nargs; + + for(nargs=0; nargs<maxargs; nargs++){ + while(*s!='\0' && utfrune(sep, *s)!=nil) + *s++ = '\0'; + if(*s == '\0') + break; + args[nargs] = s; + s = etoken(s, sep); + } + + return nargs; +} + +int +tokenize(char *s, char **args, int maxargs) +{ + int nargs; + + for(nargs=0; nargs<maxargs; nargs++){ + while(*s!='\0' && utfrune(qsep, *s)!=nil) + s++; + if(*s == '\0') + break; + args[nargs] = s; + s = qtoken(s, qsep); + } + + return nargs; +} diff --git a/sys/src/libc/port/toupper.c b/sys/src/libc/port/toupper.c new file mode 100755 index 000000000..d5fcf7b19 --- /dev/null +++ b/sys/src/libc/port/toupper.c @@ -0,0 +1,19 @@ +#include <ctype.h> + +int +toupper(int c) +{ + + if(c < 'a' || c > 'z') + return c; + return _toupper(c); +} + +int +tolower(int c) +{ + + if(c < 'A' || c > 'Z') + return c; + return _tolower(c); +} diff --git a/sys/src/libc/port/u16.c b/sys/src/libc/port/u16.c new file mode 100755 index 000000000..4e1637120 --- /dev/null +++ b/sys/src/libc/port/u16.c @@ -0,0 +1,53 @@ +#include <u.h> +#include <libc.h> +static char t16e[] = "0123456789ABCDEF"; + +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 = *in++; + if('0' <= c && c <= '9') + c = c - '0'; + else if('a' <= c && c <= 'z') + c = c - 'a' + 10; + else if('A' <= c && c <= 'Z') + c = c - 'A' + 10; + else + 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++ = t16e[c>>4]; + *out++ = t16e[c&0xf]; + } +exhausted: + *out = 0; + return out - start; +} diff --git a/sys/src/libc/port/u32.c b/sys/src/libc/port/u32.c new file mode 100755 index 000000000..7423984a2 --- /dev/null +++ b/sys/src/libc/port/u32.c @@ -0,0 +1,110 @@ +#include <u.h> +#include <libc.h> + +int +dec32(uchar *dest, int ndest, char *src, int nsrc) +{ + char *s, *tab; + uchar *start; + int i, u[8]; + + if(ndest+1 < (5*nsrc+7)/8) + return -1; + start = dest; + tab = "23456789abcdefghijkmnpqrstuvwxyz"; + while(nsrc>=8){ + for(i=0; i<8; i++){ + s = strchr(tab,(int)src[i]); + u[i] = s ? s-tab : 0; + } + *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++){ + s = strchr(tab,(int)src[i]); + u[i] = s ? s-tab : 0; + } + *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 *tab, *start; + int j; + + if(ndest <= (8*nsrc+4)/5 ) + return -1; + start = dest; + tab = "23456789abcdefghijkmnpqrstuvwxyz"; + while(nsrc>=5){ + j = (0x1f & (src[0]>>3)); + *dest++ = tab[j]; + j = (0x1c & (src[0]<<2)) | (0x03 & (src[1]>>6)); + *dest++ = tab[j]; + j = (0x1f & (src[1]>>1)); + *dest++ = tab[j]; + j = (0x10 & (src[1]<<4)) | (0x0f & (src[2]>>4)); + *dest++ = tab[j]; + j = (0x1e & (src[2]<<1)) | (0x01 & (src[3]>>7)); + *dest++ = tab[j]; + j = (0x1f & (src[3]>>2)); + *dest++ = tab[j]; + j = (0x18 & (src[3]<<3)) | (0x07 & (src[4]>>5)); + *dest++ = tab[j]; + j = (0x1f & (src[4])); + *dest++ = tab[j]; + src += 5; + nsrc -= 5; + } + if(nsrc){ + j = (0x1f & (src[0]>>3)); + *dest++ = tab[j]; + j = (0x1c & (src[0]<<2)); + if(nsrc == 1) + goto out; + j |= (0x03 & (src[1]>>6)); + *dest++ = tab[j]; + j = (0x1f & (src[1]>>1)); + if(nsrc == 2) + goto out; + *dest++ = tab[j]; + j = (0x10 & (src[1]<<4)); + if(nsrc == 3) + goto out; + j |= (0x0f & (src[2]>>4)); + *dest++ = tab[j]; + j = (0x1e & (src[2]<<1)); + if(nsrc == 4) + goto out; + j |= (0x01 & (src[3]>>7)); + *dest++ = tab[j]; + j = (0x1f & (src[3]>>2)); + *dest++ = tab[j]; + j = (0x18 & (src[3]<<3)); +out: + *dest++ = tab[j]; + } + *dest = 0; + return dest-start; +} diff --git a/sys/src/libc/port/u64.c b/sys/src/libc/port/u64.c new file mode 100755 index 000000000..bf86c634c --- /dev/null +++ b/sys/src/libc/port/u64.c @@ -0,0 +1,127 @@ +#include <u.h> +#include <libc.h> + +enum { + INVAL= 255 +}; + +static uchar t64d[256] = { + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, 62,INVAL,INVAL,INVAL, 63, + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, + 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL, + INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL,INVAL +}; +static char t64e[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; + +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 = t64d[*(uchar*)in++]; + if(c == INVAL) + 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 = -1; + break; + } + 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++ = t64e[(b24>>18)]; + *out++ = t64e[(b24>>12)&0x3f]; + *out++ = t64e[(b24>>6)&0x3f]; + *out++ = t64e[(b24)&0x3f]; + } + + switch(n%3){ + case 2: + b24 = (*in++)<<16; + b24 |= (*in)<<8; + if(out + 4 >= e) + goto exhausted; + *out++ = t64e[(b24>>18)]; + *out++ = t64e[(b24>>12)&0x3f]; + *out++ = t64e[(b24>>6)&0x3f]; + *out++ = '='; + break; + case 1: + b24 = (*in)<<16; + if(out + 4 >= e) + goto exhausted; + *out++ = t64e[(b24>>18)]; + *out++ = t64e[(b24>>12)&0x3f]; + *out++ = '='; + *out++ = '='; + break; + } +exhausted: + *out = 0; + return out - start; +} diff --git a/sys/src/libc/port/utfecpy.c b/sys/src/libc/port/utfecpy.c new file mode 100755 index 000000000..565368bdf --- /dev/null +++ b/sys/src/libc/port/utfecpy.c @@ -0,0 +1,21 @@ +#include <u.h> +#include <libc.h> + +char* +utfecpy(char *to, char *e, char *from) +{ + char *end; + + if(to >= e) + return to; + end = memccpy(to, from, '\0', e - to); + if(end == nil){ + end = e; + while(end>to && (*--end&0xC0)==0x80) + ; + *end = '\0'; + }else{ + end--; + } + return end; +} diff --git a/sys/src/libc/port/utflen.c b/sys/src/libc/port/utflen.c new file mode 100755 index 000000000..4356fb1c2 --- /dev/null +++ b/sys/src/libc/port/utflen.c @@ -0,0 +1,22 @@ +#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++; + } +} diff --git a/sys/src/libc/port/utfnlen.c b/sys/src/libc/port/utfnlen.c new file mode 100755 index 000000000..43e9c4aae --- /dev/null +++ b/sys/src/libc/port/utfnlen.c @@ -0,0 +1,26 @@ +#include <u.h> +#include <libc.h> + +int +utfnlen(char *s, long m) +{ + int c; + long n; + Rune rune; + char *es; + + es = s + m; + for(n = 0; s < es; n++) { + c = *(uchar*)s; + if(c < Runeself){ + if(c == '\0') + break; + s++; + continue; + } + if(!fullrune(s, es-s)) + break; + s += chartorune(&rune, s); + } + return n; +} diff --git a/sys/src/libc/port/utfrrune.c b/sys/src/libc/port/utfrrune.c new file mode 100755 index 000000000..c52791f88 --- /dev/null +++ b/sys/src/libc/port/utfrrune.c @@ -0,0 +1,30 @@ +#include <u.h> +#include <libc.h> + +char* +utfrrune(char *s, long c) +{ + long c1; + Rune r; + char *s1; + + if(c < Runesync) /* not part of utf sequence */ + return strrchr(s, c); + + s1 = 0; + for(;;) { + c1 = *(uchar*)s; + if(c1 < Runeself) { /* one byte rune */ + if(c1 == 0) + return s1; + if(c1 == c) + s1 = s; + s++; + continue; + } + c1 = chartorune(&r, s); + if(r == c) + s1 = s; + s += c1; + } +} diff --git a/sys/src/libc/port/utfrune.c b/sys/src/libc/port/utfrune.c new file mode 100755 index 000000000..8d975855d --- /dev/null +++ b/sys/src/libc/port/utfrune.c @@ -0,0 +1,29 @@ +#include <u.h> +#include <libc.h> + +char* +utfrune(char *s, long c) +{ + long c1; + Rune r; + int n; + + if(c < Runesync) /* not part of utf sequence */ + return strchr(s, c); + + for(;;) { + c1 = *(uchar*)s; + if(c1 < Runeself) { /* one byte rune */ + if(c1 == 0) + return 0; + if(c1 == c) + return s; + s++; + continue; + } + n = chartorune(&r, s); + if(r == c) + return s; + s += n; + } +} diff --git a/sys/src/libc/port/utfutf.c b/sys/src/libc/port/utfutf.c new file mode 100755 index 000000000..48d1ee831 --- /dev/null +++ b/sys/src/libc/port/utfutf.c @@ -0,0 +1,26 @@ +#include <u.h> +#include <libc.h> + + +/* + * Return pointer to first occurrence of s2 in s1, + * 0 if none + */ +char* +utfutf(char *s1, char *s2) +{ + char *p; + long f, n1, n2; + Rune r; + + n1 = chartorune(&r, s2); + f = r; + if(f <= Runesync) /* represents self */ + return strstr(s1, s2); + + n2 = strlen(s2); + for(p=s1; p=utfrune(p, f); p+=n1) + if(strncmp(p, s2, n2) == 0) + return p; + return 0; +} |