diff options
author | Karl Berry <karl@freefriends.org> | 2018-04-03 22:35:04 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2018-04-03 22:35:04 +0000 |
commit | 36b8d1341af4a7ab1f5759d75ad1eecfc375c1f4 (patch) | |
tree | 12d09b686d2c18f245dc6fd492c09cdcd4c02ebc /Build/source/utils/asymptote/runmath.in | |
parent | d73e029b665b866fe734e44508746a2cba513fd7 (diff) |
asy 2.42 sources
git-svn-id: svn://tug.org/texlive/trunk@47274 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/utils/asymptote/runmath.in')
-rw-r--r-- | Build/source/utils/asymptote/runmath.in | 156 |
1 files changed, 142 insertions, 14 deletions
diff --git a/Build/source/utils/asymptote/runmath.in b/Build/source/utils/asymptote/runmath.in index 88ca420a399..f64d3117d4a 100644 --- a/Build/source/utils/asymptote/runmath.in +++ b/Build/source/utils/asymptote/runmath.in @@ -34,6 +34,118 @@ const char *invalidargument="invalid argument"; extern uint32_t CLZ(uint32_t a); +inline unsigned intbits() { + static unsigned count=0; + if(count > 0) return count; + while((1UL << count) < Int_MAX) + ++count; + ++count; + return count; +} + +static const unsigned char BitReverseTable8[256]= +{ +#define R2(n) n, n+2*64, n+1*64, n+3*64 +#define R4(n) R2(n),R2(n+2*16),R2(n+1*16),R2(n+3*16) +#define R6(n) R4(n),R4(n+2*4 ),R4(n+1*4 ),R4(n+3*4 ) +R6(0),R6(2),R6(1),R6(3) +}; +#undef R2 +#undef R4 +#undef R6 + +unsigned long long bitreverse8(unsigned long long a) +{ + return + (unsigned long long) BitReverseTable8[a]; +} + +unsigned long long bitreverse16(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 8)]); +} + +unsigned long long bitreverse24(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 16) | + ((unsigned long long) BitReverseTable8[(a >> 8) & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 16)]); +} + +unsigned long long bitreverse32(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 24) | + ((unsigned long long) BitReverseTable8[(a >> 8) & 0xff] << 16) | + ((unsigned long long) BitReverseTable8[(a >> 16) & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 24)]); +} + +unsigned long long bitreverse40(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 32) | + ((unsigned long long) BitReverseTable8[(a >> 8) & 0xff] << 24) | + ((unsigned long long) BitReverseTable8[(a >> 16) & 0xff] << 16) | + ((unsigned long long) BitReverseTable8[(a >> 24) & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 32)]); +} + +unsigned long long bitreverse48(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 40) | + ((unsigned long long) BitReverseTable8[(a >> 8) & 0xff] << 32) | + ((unsigned long long) BitReverseTable8[(a >> 16) & 0xff] << 24) | + ((unsigned long long) BitReverseTable8[(a >> 24) & 0xff] << 16) | + ((unsigned long long) BitReverseTable8[(a >> 32) & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 40)]); +} + +unsigned long long bitreverse56(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 48) | + ((unsigned long long) BitReverseTable8[(a >> 8) & 0xff] << 40) | + ((unsigned long long) BitReverseTable8[(a >> 16) & 0xff] << 32) | + ((unsigned long long) BitReverseTable8[(a >> 24) & 0xff] << 24) | + ((unsigned long long) BitReverseTable8[(a >> 32) & 0xff] << 16) | + ((unsigned long long) BitReverseTable8[(a >> 40) & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 48)]); +} + +unsigned long long bitreverse64(unsigned long long a) +{ + return + ((unsigned long long) BitReverseTable8[a & 0xff] << 56) | + ((unsigned long long) BitReverseTable8[(a >> 8) & 0xff] << 48) | + ((unsigned long long) BitReverseTable8[(a >> 16) & 0xff] << 40) | + ((unsigned long long) BitReverseTable8[(a >> 24) & 0xff] << 32) | + ((unsigned long long) BitReverseTable8[(a >> 32) & 0xff] << 24) | + ((unsigned long long) BitReverseTable8[(a >> 40) & 0xff] << 16) | + ((unsigned long long) BitReverseTable8[(a >> 48) & 0xff] << 8) | + ((unsigned long long) BitReverseTable8[(a >> 56)]); +} + +// From Warren, Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). +// Addison Wesley - Pearson Education, Inc. pp. 81-96. +Int popcount(Int a) +{ + const uint64_t m1 = 0x5555555555555555; //binary: 0101... + const uint64_t m2 = 0x3333333333333333; //binary: 00110011.. + const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ... + const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3... + +// This algorithm uses 12 arithmetic operations, one of which is a multiply. + a -= (a >> 1) & m1; //put count of each 2 bits into those 2 bits + a=(a & m2)+((a >> 2) & m2); //put count of each 4 bits into those 4 bits + a=(a+(a >> 4)) & m4; //put count of each 8 bits into those 8 bits + return (a * h01) >> 56; //returns left 8 bits of a+(a << 8)+(a << 16)+(a << 24)+... +} + // Return the factorial of a non-negative integer using a lookup table. Int factorial(Int n) { @@ -300,22 +412,38 @@ Int NOT(Int a) Int CLZ(Int a) { - if((uint32_t) a > 0xFFFFFFFF) return -1; - return CLZ((uint32_t) a); + if((unsignedInt) a > 0xFFFFFFFF) + return CLZ((uint32_t) (a >> 32)); + else { + int bits=intbits(); + if(a != 0) return bits-32+CLZ((uint32_t) a); + return bits; + } +} + +Int popcount(Int a) +{ + return popcount(a); } Int CTZ(Int a) { - if((uint32_t) a > 0xFFFFFFFF) return -1; -#if __GNUC__ - return __builtin_ctz(a); -#else - // find the number of trailing zeros in a 32-bit number - static const int MultiplyDeBruijnBitPosition[32] = { - 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, - 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 - }; - return MultiplyDeBruijnBitPosition[((uint32_t)((a & -a) * 0x077CB531U)) - >> 27]; -#endif + return popcount((a&-a)-1); +} + +// bitreverse a within a word of length bits. +Int bitreverse(Int a, Int bits) +{ + typedef unsigned long long Bitreverse(unsigned long long a); + static Bitreverse *B[]={bitreverse8,bitreverse16,bitreverse24,bitreverse32, + bitreverse40,bitreverse48,bitreverse56,bitreverse64}; + int maxbits=intbits()-1; // Drop sign bit +#if Int_MAX2 >= 0x7fffffffffffffffLL + --maxbits; // Drop extra bit for reserved values +#endif + if(bits <= 0 || bits > maxbits || a < 0 || + (unsigned long long) a >= (1ULL << bits)) + return -1; + unsigned int bytes=(bits+7)/8; + return B[bytes-1]((unsigned long long) a) >> (8*bytes-bits); } |