1 #if !defined HAVE_BITTRANSFORMS_H__ 2 #define HAVE_BITTRANSFORMS_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2010 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 #include "fxttypes.h" 9 #include "bits/bitsperlong.h" 10 11 blue_code(ulong a)12static inline ulong blue_code(ulong a) 13 // Self-inverse. 14 // range [0..2^k-1] is mapped onto itself 15 // work \prop log_2(BITS_PER_LONG) 16 //. 17 // With B:=blue, G:=gray, I:=inverse_gray 18 // G(B(G(B(a)))) == a 19 // G(B(G(a))) == B(a) 20 // I(B(I(a))) == B(a) 21 // G(B(a)) == B(I(a)) 22 // With P:=parity 23 // P(B(a)) == a % 2 24 { 25 ulong s = BITS_PER_LONG >> 1; 26 ulong m = ~0UL << s; 27 do 28 { 29 a ^= ( (a&m) >> s ); 30 s >>= 1; 31 m ^= (m>>s); 32 } 33 while ( s ); 34 return a; 35 } 36 // ------------------------- 37 38 39 yellow_code(ulong a)40static inline ulong yellow_code(ulong a) 41 // Self-inverse. 42 // work \prop log_2(BITS_PER_LONG) 43 //. 44 // With Y:=yellow, B:=blue, r:=revbin 45 // B(a) == Y(r(Y(a))) 46 // Y(a) == r(B(r(a))) 47 // r(a) == Y(B(Y(a))) == B(Y(B(a))) 48 // With P:=parity 49 // P(Y(a)) == highest_one(a) == "sign(a)" 50 { 51 ulong s = BITS_PER_LONG >> 1; 52 ulong m = ~0UL >> s; 53 do 54 { 55 a ^= ( (a&m) << s ); 56 s >>= 1; 57 m ^= (m<<s); 58 } 59 while ( s ); 60 return a; 61 } 62 // ------------------------- 63 64 red_code(ulong a)65static inline ulong red_code(ulong a) 66 // work \prop log_2(BITS_PER_LONG) 67 // =^= revbin( blue_code(a) ); 68 { 69 ulong s = BITS_PER_LONG >> 1; 70 ulong m = ~0UL >> s; 71 do 72 { 73 ulong u = a & m; 74 ulong v = a ^ u; 75 a = v ^ (u<<s); 76 a ^= (v>>s); 77 s >>= 1; 78 m ^= (m<<s); 79 } 80 while ( s ); 81 return a; 82 } 83 // ------------------------- 84 85 green_code(ulong a)86static inline ulong green_code(ulong a) 87 // work \prop log_2(BITS_PER_LONG) 88 // =^= revbin( yellow_code(a) ); 89 { 90 ulong s = BITS_PER_LONG >> 1; 91 ulong m = ~0UL << s; 92 do 93 { 94 ulong u = a & m; 95 ulong v = a ^ u; 96 a = v ^ (u>>s); 97 a ^= (v<<s); 98 s >>= 1; 99 m ^= (m>>s); 100 } 101 while ( s ); 102 return a; 103 } 104 // ------------------------- 105 106 107 #endif // !defined HAVE_BITTRANSFORMS_H__ 108