bits.c (2245B)
1 #include "bits.h" 2 #include "rcx.h" 3 4 /* To perform a bit zip with n inputs, we evaluate, over the integers mod 2 5 * (where XOR is addition and AND is multiplication), a recursively-structured 6 * polynomial with n variables, 2^n terms, and coefficients f0,f1,...,f(2^n-1), 7 * the bits of the zipping function f. The pattern is illustrated below for the 8 * first few values of n. In principle, we do this independently for each of 9 * the 64 n-tuples of input bits, but C's bit-wise operators let us do all 64 10 * evaluations in parallel. */ 11 12 /* This is the constant polynomial f0. We use a two's complement trick to 13 * broadcast f0 to an entire u64. */ 14 static inline u64 bz0(u64 f) { 15 return !(f & 1u) - 1u; 16 } 17 18 /* f0 ^ 19 * f1 & u */ 20 static inline u64 bz1(u64 f, u64 u) { 21 return bz0(f) ^ (bz0(f >> 1) & u); 22 } 23 24 /* f0 ^ 25 * f1 & u ^ 26 * f2 & v ^ 27 * f3 & u & v */ 28 static inline u64 bz2(u64 f, u64 u, u64 v) { 29 return bz1(f, u) ^ (bz1(f >> 2, u) & v); 30 } 31 32 /* f0 ^ 33 * f1 & u ^ 34 * f2 & v ^ 35 * f3 & u & v ^ 36 * f4 & w ^ 37 * f5 & u & w ^ 38 * f6 & v & w ^ 39 * f7 & u & v & w */ 40 static inline u64 bz3(u64 f, u64 u, u64 v, u64 w) { 41 return bz2(f, u, v) ^ (bz2(f >> 4, u, v) & w); 42 } 43 44 /* Etc... */ 45 static inline u64 bz4(u64 f, u64 u, u64 v, u64 w, u64 x) { 46 return bz3(f, u, v, w) ^ (bz3(f >> 8, u, v, w) & x); 47 } 48 49 static inline u64 bz5(u64 f, u64 u, u64 v, u64 w, u64 x, u64 y) { 50 return bz4(f, u, v, w, x) ^ (bz4(f >> 16, u, v, w, x) & y); 51 } 52 53 static inline u64 bz6(u64 f, u64 u, u64 v, u64 w, u64 x, u64 y, u64 z) { 54 return bz5(f, u, v, w, x, y) ^ (bz5(f >> 32, u, v, w, x, y) & z); 55 } 56 57 u64 r_bz0(u64 f) { return bz0(f); } 58 u64 r_bz1(u64 f, u64 u) { return bz1(f, u); } 59 u64 r_bz2(u64 f, u64 u, u64 v) { return bz2(f, u, v); } 60 u64 r_bz3(u64 f, u64 u, u64 v, u64 w) { return bz3(f, u, v, w); } 61 u64 r_bz4(u64 f, u64 u, u64 v, u64 w, u64 x) { return bz4(f, u, v, w, x); } 62 u64 r_bz5(u64 f, u64 u, u64 v, u64 w, u64 x, u64 y) { return bz5(f, u, v, w, x, y); } 63 u64 r_bz6(u64 f, u64 u, u64 v, u64 w, u64 x, u64 y, u64 z) { return bz6(f, u, v, w, x, y, z); }