1 #if !defined HAVE_GRAYCODE_H__
2 #define HAVE_GRAYCODE_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010, 2012 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
gray_code(ulong x)12 static inline ulong gray_code(ulong x)
13 // Return the Gray code of x
14 // ('bit-wise derivative modulo 2')
15 {
16 return x ^ (x>>1);
17 }
18 // -------------------------
19
20
inverse_gray_code(ulong x)21 static inline ulong inverse_gray_code(ulong x)
22 // inverse of gray_code()
23 // note: the returned value contains at each bit position
24 // the parity of all bits of the input left from it (incl. itself)
25 //
26 {
27 // ----- VERSION 1 (integration modulo 2):
28 // ulong h=1, r=0;
29 // do
30 // {
31 // if ( x & 1 ) r^=h;
32 // x >>= 1;
33 // h = (h<<1)+1;
34 // }
35 // while ( x!=0 );
36 // return r;
37
38 // ----- VERSION 2 (apply graycode BITS_PER_LONG-1 times):
39 // ulong r = BITS_PER_LONG;
40 // while ( --r ) x ^= x>>1;
41 // return x;
42
43 // ----- VERSION 3 (use: gray ** BITSPERLONG == id):
44 x ^= x>>1; // gray ** 1
45 x ^= x>>2; // gray ** 2
46 x ^= x>>4; // gray ** 4
47 x ^= x>>8; // gray ** 8
48 x ^= x>>16; // gray ** 16
49 // here: x = gray**31(input)
50 // note: the statements can be reordered at will
51
52 #if BITS_PER_LONG > 32
53 x ^= x>>32; // for 64bit words
54 #endif
55
56 return x;
57 }
58 // -------------------------
59
60
byte_gray_code(ulong x)61 static inline ulong byte_gray_code(ulong x)
62 // Return the Gray code of bytes in parallel
63 {
64 #if BITS_PER_LONG == 32
65 return x ^ ((x & 0xfefefefeUL)>>1);
66 #endif
67
68 #if BITS_PER_LONG == 64
69 return x ^ ((x & 0xfefefefefefefefeUL)>>1);
70 #endif
71 }
72 // -------------------------
73
byte_inverse_gray_code(ulong x)74 static inline ulong byte_inverse_gray_code(ulong x)
75 // Return the inverse Gray code of bytes in parallel
76 {
77 #if BITS_PER_LONG == 32
78 x ^= ((x & 0xfefefefeUL)>>1);
79 x ^= ((x & 0xfcfcfcfcUL)>>2);
80 x ^= ((x & 0xf0f0f0f0UL)>>4);
81 #endif
82
83 #if BITS_PER_LONG == 64
84 x ^= ((x & 0xfefefefefefefefeUL)>>1);
85 x ^= ((x & 0xfcfcfcfcfcfcfcfcUL)>>2);
86 x ^= ((x & 0xf0f0f0f0f0f0f0f0UL)>>4);
87 #endif
88
89 return x;
90 }
91 // -------------------------
92
93
94 #endif // !defined HAVE_GRAYCODE_H__
95