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)12 static 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)40 static 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)65 static 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)86 static 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