summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/runmath.in
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2018-04-03 22:35:04 +0000
committerKarl Berry <karl@freefriends.org>2018-04-03 22:35:04 +0000
commit36b8d1341af4a7ab1f5759d75ad1eecfc375c1f4 (patch)
tree12d09b686d2c18f245dc6fd492c09cdcd4c02ebc /Build/source/utils/asymptote/runmath.in
parentd73e029b665b866fe734e44508746a2cba513fd7 (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.in156
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);
}