1 #if !defined HAVE_REVGRAYCODE_H__
2 #define HAVE_REVGRAYCODE_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
rev_gray_code(ulong x)12 static inline ulong rev_gray_code(ulong x)
13 // Return the reversed Gray code of x.
14 // ('bit-wise derivative modulo 2 towards high bits').
15 // Also: multiplication by x+1 as binary polynomial.
16 // Also: return x^2+x in binary normal basis.
17 // rev_gray_code(x) == revbin( gray_code( revbin(x) ) )
18 {
19 return x ^ (x<<1);
20 }
21 // -------------------------
22
23
inverse_rev_gray_code(ulong x)24 static inline ulong inverse_rev_gray_code(ulong x)
25 // Inverse of rev_gray_code()
26 // Note: the returned value contains at each bit position the parity
27 // of all bits of the input right from it (incl. itself).
28 // Also: division by x+1 as powers series over GF(2)
29 // Also: return solution of z = x^2+x in binary normal basis.
30 // Note: the statements can be reordered at will.
31 // inverse_rev_gray_code(x) == revbin( inverse_gray_code( revbin(x) ) )
32 {
33 // use: rev_gray ** BITSPERLONG == id:
34 x ^= x<<1; // rev_gray ** 1
35 x ^= x<<2; // rev_gray ** 2
36 x ^= x<<4; // rev_gray ** 4
37 x ^= x<<8; // rev_gray ** 8
38 x ^= x<<16; // rev_gray ** 16
39 // here: x = rev_gray**31(input)
40 #if BITS_PER_LONG >= 64
41 x ^= x<<32; // for 64bit words
42 #endif
43 return x;
44 }
45 // -------------------------
46
47
48
49 #endif // !defined HAVE_REVGRAYCODE_H__
50