﻿ NumericsHelpers.cs
 File: System\Numerics\NumericsHelpers.cs Project: ndp\fx\src\Numerics\System.Numerics.csproj (System.Numerics)
 ```// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== using System; using System.Diagnostics; using System.Diagnostics.Contracts; using System.Collections.Generic; using System.Runtime.InteropServices; using System.Text; namespace System.Numerics { [StructLayout(LayoutKind.Explicit)] internal struct DoubleUlong { [FieldOffset(0)] public double dbl; [FieldOffset(0)] public ulong uu; } internal static class NumericsHelpers { private const int kcbitUint = 32; public static void GetDoubleParts(double dbl, out int sign, out int exp, out ulong man, out bool fFinite) { Contract.Ensures(Contract.ValueAtReturn(out sign) == +1 || Contract.ValueAtReturn(out sign) == -1); DoubleUlong du; du.uu = 0; du.dbl = dbl; sign = 1 - ((int)(du.uu >> 62) & 2); man = du.uu & 0x000FFFFFFFFFFFFF; exp = (int)(du.uu >> 52) & 0x7FF; if (exp == 0) { // Denormalized number. fFinite = true; if (man != 0) exp = -1074; } else if (exp == 0x7FF) { // NaN or Inifite. fFinite = false; exp = int.MaxValue; } else { fFinite = true; man |= 0x0010000000000000; exp -= 1075; } } public static double GetDoubleFromParts(int sign, int exp, ulong man) { DoubleUlong du; du.dbl = 0; if (man == 0) du.uu = 0; else { // Normalize so that 0x0010 0000 0000 0000 is the highest bit set. int cbitShift = CbitHighZero(man) - 11; if (cbitShift < 0) man >>= -cbitShift; else man <<= cbitShift; exp -= cbitShift; Contract.Assert((man & 0xFFF0000000000000) == 0x0010000000000000); // Move the point to just behind the leading 1: 0x001.0 0000 0000 0000 // (52 bits) and skew the exponent (by 0x3FF == 1023). exp += 1075; if (exp >= 0x7FF) { // Infinity. du.uu = 0x7FF0000000000000; } else if (exp <= 0) { // Denormalized. exp--; if (exp < -52) { // Underflow to zero. du.uu = 0; } else { du.uu = man >> -exp; Contract.Assert(du.uu != 0); } } else { // Mask off the implicit high bit. du.uu = (man & 0x000FFFFFFFFFFFFF) | ((ulong)exp << 52); } } if (sign < 0) du.uu |= 0x8000000000000000; return du.dbl; } // Do an in-place twos complement of d and also return the result. // "Dangerous" because it causes a mutation and needs to be used // with care for immutable types public static uint[] DangerousMakeTwosComplement(uint[] d) { // first do complement and +1 as long as carry is needed int i = 0; uint v = 0; for (; i < d.Length; i++) { v = ~d[i] + 1; d[i] = v; if (v != 0) { i++; break; } } if (v != 0) { // now ones complement is sufficient for (; i < d.Length; i++) { d[i] = ~d[i]; } } else { //??? this is weird d = resize(d, d.Length + 1); d[d.Length - 1] = 1; } return d; } public static uint[] resize(uint[] v, int len) { if (v.Length == len) return v; uint[] ret = new uint[len]; int n = System.Math.Min(v.Length, len); for (int i = 0; i < n; i++) { ret[i] = v[i]; } return ret; } public static void Swap(ref T a, ref T b) { T tmp = a; a = b; b = tmp; } public static uint GCD(uint u1, uint u2) { const int cvMax = 32; if (u1 < u2) goto LOther; LTop: Contract.Assert(u2 <= u1); if (u2 == 0) return u1; for (int cv = cvMax; ; ) { u1 -= u2; if (u1 < u2) break; if (--cv == 0) { u1 %= u2; break; } } LOther: Contract.Assert(u1 < u2); if (u1 == 0) return u2; for (int cv = cvMax; ; ) { u2 -= u1; if (u2 < u1) break; if (--cv == 0) { u2 %= u1; break; } } goto LTop; } public static ulong GCD(ulong uu1, ulong uu2) { const int cvMax = 32; if (uu1 < uu2) goto LOther; LTop: Contract.Assert(uu2 <= uu1); if (uu1 <= uint.MaxValue) goto LSmall; if (uu2 == 0) return uu1; for (int cv = cvMax; ; ) { uu1 -= uu2; if (uu1 < uu2) break; if (--cv == 0) { uu1 %= uu2; break; } } LOther: Contract.Assert(uu1 < uu2); if (uu2 <= uint.MaxValue) goto LSmall; if (uu1 == 0) return uu2; for (int cv = cvMax; ; ) { uu2 -= uu1; if (uu2 < uu1) break; if (--cv == 0) { uu2 %= uu1; break; } } goto LTop; LSmall: uint u1 = (uint)uu1; uint u2 = (uint)uu2; if (u1 < u2) goto LOtherSmall; LTopSmall: Contract.Assert(u2 <= u1); if (u2 == 0) return u1; for (int cv = cvMax; ; ) { u1 -= u2; if (u1 < u2) break; if (--cv == 0) { u1 %= u2; break; } } LOtherSmall: Contract.Assert(u1 < u2); if (u1 == 0) return u2; for (int cv = cvMax; ; ) { u2 -= u1; if (u2 < u1) break; if (--cv == 0) { u2 %= u1; break; } } goto LTopSmall; } public static ulong MakeUlong(uint uHi, uint uLo) { return ((ulong)uHi << kcbitUint) | uLo; } public static uint GetLo(ulong uu) { return (uint)uu; } public static uint GetHi(ulong uu) { return (uint)(uu >> kcbitUint); } public static uint Abs(int a) { uint mask = (uint)(a >> 31); return ((uint)a ^ mask) - mask; } // public static ulong Abs(long a) { // ulong mask = (ulong)(a >> 63); // return ((ulong)a ^ mask) - mask; // } public static uint CombineHash(uint u1, uint u2) { return ((u1 << 7) | (u1 >> 25)) ^ u2; } public static int CombineHash(int n1, int n2) { return (int)CombineHash((uint)n1, (uint)n2); } public static int CbitHighZero(uint u) { if (u == 0) return 32; int cbit = 0; if ((u & 0xFFFF0000) == 0) { cbit += 16; u <<= 16; } if ((u & 0xFF000000) == 0) { cbit += 8; u <<= 8; } if ((u & 0xF0000000) == 0) { cbit += 4; u <<= 4; } if ((u & 0xC0000000) == 0) { cbit += 2; u <<= 2; } if ((u & 0x80000000) == 0) cbit += 1; return cbit; } public static int CbitLowZero(uint u) { if (u == 0) return 32; int cbit = 0; if ((u & 0x0000FFFF) == 0) { cbit += 16; u >>= 16; } if ((u & 0x000000FF) == 0) { cbit += 8; u >>= 8; } if ((u & 0x0000000F) == 0) { cbit += 4; u >>= 4; } if ((u & 0x00000003) == 0) { cbit += 2; u >>= 2; } if ((u & 0x00000001) == 0) cbit += 1; return cbit; } public static int CbitHighZero(ulong uu) { if ((uu & 0xFFFFFFFF00000000) == 0) return 32 + CbitHighZero((uint)uu); return CbitHighZero((uint)(uu >> 32)); } // public static int CbitLowZero(ulong uu) { // if ((uint)uu == 0) // return 32 + CbitLowZero((uint)(uu >> 32)); // return CbitLowZero((uint)uu); // } // // public static int Cbit(uint u) { // u = (u & 0x55555555) + ((u >> 1) & 0x55555555); // u = (u & 0x33333333) + ((u >> 2) & 0x33333333); // u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F); // u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF); // return (int)((ushort)u + (ushort)(u >> 16)); // } // // static int Cbit(ulong uu) { // uu = (uu & 0x5555555555555555) + ((uu >> 1) & 0x5555555555555555); // uu = (uu & 0x3333333333333333) + ((uu >> 2) & 0x3333333333333333); // uu = (uu & 0x0F0F0F0F0F0F0F0F) + ((uu >> 4) & 0x0F0F0F0F0F0F0F0F); // uu = (uu & 0x00FF00FF00FF00FF) + ((uu >> 8) & 0x00FF00FF00FF00FF); // uu = (uu & 0x0000FFFF0000FFFF) + ((uu >> 16) & 0x0000FFFF0000FFFF); // return (int)((uint)uu + (uint)(uu >> 32)); // } } } ```