1 /** Bijections between scalar types and integers. 2 * 3 * TOOD extract reinterpret!T(x) 4 * 5 * TODO support `real`? 6 */ 7 module nxt.bijections; 8 9 import std.meta : AliasSeq, staticIndexOf; 10 import std.traits : Unqual, isUnsigned, isSigned, isIntegral, Unsigned, Signed, isNumeric, isSomeChar; 11 12 /** List of types that are bijectable to builtin integral types. */ 13 alias IntegralBijectableTypes = AliasSeq!(bool, char, wchar, dchar, 14 ubyte, ushort, uint, ulong, 15 byte, short, int, long, 16 float, double); 17 18 enum isIntegralBijectableType(T) = staticIndexOf!(Unqual!T, IntegralBijectableTypes) >= 0; 19 20 /// check that `bijectToUnsigned` preserves orderness, that is is a bijection 21 @safe unittest 22 { 23 import std.random : Random, uniform; 24 auto gen = Random(); 25 26 enum maxCount = 1e4; 27 import std.algorithm : min; 28 29 static int cmp(T)(T x, T y) { return x < y ? -1 : x > y ? 1 : 0; } 30 31 foreach (T; AliasSeq!(ubyte, ushort, uint, ulong, 32 byte, short, int, long)) 33 { 34 foreach (i; 0 .. min(maxCount, T.max - T.min)) 35 { 36 const x = uniform(T.min, T.max, gen); 37 const y = uniform(T.min, T.max, gen); 38 39 const expected = cmp(x, 40 y); 41 const result = cmp(x.bijectToUnsigned, 42 y.bijectToUnsigned); 43 44 assert(result == expected); 45 } 46 } 47 48 foreach (T; AliasSeq!(float, double)) 49 { 50 foreach (i; 0 .. maxCount) 51 { 52 const T x = uniform(-1e20, +1e20, gen); 53 const T y = uniform(-1e20, +1e20, gen); 54 55 // import nxt.dbgio; 56 // dbg(x, ",", y); 57 58 const expected = cmp(x, 59 y); 60 const result = cmp(x.bijectToUnsigned, 61 y.bijectToUnsigned); 62 63 assert(result == expected); 64 } 65 } 66 } 67 68 pragma(inline) @safe pure nothrow @nogc: 69 70 /** Biject (shift) a signed `a` "up" to the corresponding unsigned type (for 71 * instance before radix sorting an array of `a`). 72 */ 73 auto bijectToUnsigned(T)(T a) @trusted 74 if (isIntegralBijectableType!T) 75 { 76 alias UT = Unqual!T; 77 static if (is(UT == bool)) { return *(cast(ubyte*)&a); } // reinterpret 78 else static if (is(UT == char)) { return *(cast(ubyte*)&a); } // reinterpret 79 else static if (is(UT == wchar)) { return *(cast(ushort*)&a); } // reinterpret 80 else static if (is(UT == dchar)) { return *(cast(uint*)&a); } // reinterpret 81 else static if (isIntegral!UT) 82 { 83 static if (isSigned!UT) 84 { 85 alias UUT = Unsigned!UT; 86 return cast(UUT)(a + (cast(UUT)1 << (8*UT.sizeof - 1))); // "add up"" 87 } 88 else static if (isUnsigned!UT) 89 { 90 return a; // identity 91 } 92 else 93 { 94 static assert(0, "Unsupported integral input type " ~ UT.stringof); 95 } 96 } 97 else static if (is(UT == float)) { return ff(*cast(uint*)(&a)); } 98 else static if (is(UT == double)) { return ff(*cast(ulong*)(&a)); } 99 else static assert(0, "Unsupported input type " ~ UT.stringof); 100 } 101 102 /** Same as `bijectToUnsigned` with extra argument `descending` that reverses 103 * order. 104 */ 105 auto bijectToUnsigned(T)(T a, bool descending) 106 if (isIntegralBijectableType!T) 107 { 108 immutable ua = a.bijectToUnsigned; 109 return descending ? ua.max-ua : ua; 110 } 111 112 /** Biject (Shift) an unsigned `a` "back down" to the corresponding signed type 113 * (for instance after radix sorting an array of `a`). 114 */ 115 void bijectFromUnsigned(U)(U a, ref U b) 116 if (isUnsigned!U) 117 { 118 b = a; /// Identity. 119 } 120 121 /// ditto 122 void bijectFromUnsigned(U, V)(U a, ref V b) 123 if (isUnsigned!U && 124 isIntegral!V && isSigned!V && 125 is(U == Unsigned!V)) 126 { 127 b = a - (cast(Unsigned!U)1 << (8*U.sizeof - 1)); // "add down"" 128 } 129 130 /// ditto 131 @trusted void bijectFromUnsigned(ubyte a, ref bool b) { b = *cast(typeof(b)*)(&a); } 132 /// ditto 133 @trusted void bijectFromUnsigned(ubyte a, ref char b) { b = *cast(typeof(b)*)(&a); } 134 /// ditto 135 @trusted void bijectFromUnsigned(ushort a, ref wchar b) { b = *cast(typeof(b)*)(&a); } 136 /// ditto 137 @trusted void bijectFromUnsigned(ulong a, ref dchar b) { b = *cast(typeof(b)*)(&a); } 138 /// ditto 139 @trusted void bijectFromUnsigned(uint a, ref float b) { uint t = iff(a); b = *cast(float*)(&t); } 140 /// ditto 141 @trusted void bijectFromUnsigned(ulong a, ref double b) { ulong t = iff(a); b = *cast(double*)(&t); } 142 143 /// check that `bijectToUnsigned` is the opposite of `bijectFromUnsigned` 144 @safe pure nothrow @nogc unittest 145 { 146 foreach (T; AliasSeq!(ubyte, ushort, uint, ulong)) 147 { 148 static assert(is(typeof(T.init.bijectToUnsigned) == T)); 149 } 150 foreach (T; AliasSeq!(byte, short, int, long)) 151 { 152 static assert(is(typeof(T.init.bijectToUnsigned) == Unsigned!T)); 153 } 154 155 static assert(is(typeof(char.init.bijectToUnsigned) == ubyte)); 156 static assert(is(typeof(wchar.init.bijectToUnsigned) == ushort)); 157 static assert(is(typeof(dchar.init.bijectToUnsigned) == uint)); 158 159 const n = 1_000_000; 160 foreach (const i; 0 .. n) 161 { 162 foreach (T; AliasSeq!(bool, 163 ubyte, ushort, uint, ulong, 164 byte, short, int, long, 165 char, wchar, dchar, 166 float, double)) 167 { 168 const T x = cast(T)i; 169 auto y = x.bijectToUnsigned; 170 // pragma(msg, "T:", T); 171 // pragma(msg, "typeof(x):", typeof(x)); 172 // pragma(msg, "typeof(y):", typeof(y)); 173 T z; y.bijectFromUnsigned(z); 174 assert(x == z); 175 } 176 } 177 } 178 179 /** Map bits of floating point number \p a to unsigned integer that can be radix sorted. 180 * 181 * Also finds \em sign of \p a. 182 * 183 * - if it's 1 (negative float), it flips all bits. 184 * - if it's 0 (positive float), it flips the sign only. 185 */ 186 uint ff(uint f) { return f ^ (-cast(uint) (f >> (8*f.sizeof-1)) | 0x80000000); } 187 /// ditto 188 ulong ff(ulong f) { return f ^ (-cast(ulong) (f >> (8*f.sizeof-1)) | 0x8000000000000000); } 189 190 /** Map a floating point number \p a back from radix sorting 191 * 192 * (Inverse of \c radix_flip_float()). 193 * 194 * - if sign is 1 (negative), it flips the sign bit back 195 * - if sign is 0 (positive), it flips all bits back 196 */ 197 uint iff(uint f) { return f ^ (((f >> (8*f.sizeof-1)) - 1) | 0x80000000); } 198 /// ditto 199 ulong iff(ulong f) { return f ^ (((f >> (8*f.sizeof-1)) - 1) | 0x8000000000000000); }