--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/*
+ Copyright (c) 2005 Eliot Dresselhaus
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be
+ included in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#ifndef included_clib_bitops_h
+#define included_clib_bitops_h
+
+#include <vppinfra/clib.h>
+
+/* Population count from Hacker's Delight. */
+always_inline uword
+count_set_bits (uword x)
+{
+#if uword_bits == 64
+ const uword c1 = 0x5555555555555555;
+ const uword c2 = 0x3333333333333333;
+ const uword c3 = 0x0f0f0f0f0f0f0f0f;
+#else
+ const uword c1 = 0x55555555;
+ const uword c2 = 0x33333333;
+ const uword c3 = 0x0f0f0f0f;
+#endif
+
+ /* Sum 1 bit at a time. */
+ x = x - ((x >> (uword) 1) & c1);
+
+ /* 2 bits at a time. */
+ x = (x & c2) + ((x >> (uword) 2) & c2);
+
+ /* 4 bits at a time. */
+ x = (x + (x >> (uword) 4)) & c3;
+
+ /* 8, 16, 32 bits at a time. */
+ x = x + (x >> (uword) 8);
+ x = x + (x >> (uword) 16);
+#if uword_bits == 64
+ x = x + (x >> (uword) 32);
+#endif
+
+ return x & (2 * BITS (uword) - 1);
+}
+
+/* Based on "Hacker's Delight" code from GLS. */
+typedef struct
+{
+ uword masks[1 + log2_uword_bits];
+} compress_main_t;
+
+always_inline void
+compress_init (compress_main_t * cm, uword mask)
+{
+ uword q, m, zm, n, i;
+
+ m = ~mask;
+ zm = mask;
+
+ cm->masks[0] = mask;
+ for (i = 0; i < log2_uword_bits; i++)
+ {
+ q = m;
+ m ^= m << 1;
+ m ^= m << 2;
+ m ^= m << 4;
+ m ^= m << 8;
+ m ^= m << 16;
+#if uword_bits > 32
+ m ^= m << (uword) 32;
+#endif
+ cm->masks[1 + i] = n = (m << 1) & zm;
+ m = q & ~m;
+ q = zm & n;
+ zm = zm ^ q ^ (q >> (1 << i));
+ }
+}
+
+always_inline uword
+compress_bits (compress_main_t * cm, uword x)
+{
+ uword q, r;
+
+ r = x & cm->masks[0];
+ q = r & cm->masks[1];
+ r ^= q ^ (q >> 1);
+ q = r & cm->masks[2];
+ r ^= q ^ (q >> 2);
+ q = r & cm->masks[3];
+ r ^= q ^ (q >> 4);
+ q = r & cm->masks[4];
+ r ^= q ^ (q >> 8);
+ q = r & cm->masks[5];
+ r ^= q ^ (q >> 16);
+#if uword_bits > 32
+ q = r & cm->masks[6];
+ r ^= q ^ (q >> (uword) 32);
+#endif
+
+ return r;
+}
+
+always_inline uword
+rotate_left (uword x, uword i)
+{
+ return (x << i) | (x >> (BITS (i) - i));
+}
+
+always_inline uword
+rotate_right (uword x, uword i)
+{
+ return (x >> i) | (x << (BITS (i) - i));
+}
+
+/* Returns snoob from Hacker's Delight. Next highest number
+ with same number of set bits. */
+always_inline uword
+next_with_same_number_of_set_bits (uword x)
+{
+ uword smallest, ripple, ones;
+ smallest = x & -x;
+ ripple = x + smallest;
+ ones = x ^ ripple;
+ ones = ones >> (2 + log2_first_set (x));
+ return ripple | ones;
+}
+
+#define foreach_set_bit(var,mask,body) \
+do { \
+ uword _foreach_set_bit_m_##var = (mask); \
+ uword _foreach_set_bit_f_##var; \
+ while (_foreach_set_bit_m_##var != 0) \
+ { \
+ _foreach_set_bit_f_##var = first_set (_foreach_set_bit_m_##var); \
+ _foreach_set_bit_m_##var ^= _foreach_set_bit_f_##var; \
+ (var) = min_log2 (_foreach_set_bit_f_##var); \
+ do { body; } while (0); \
+ } \
+} while (0)
+
+#endif /* included_clib_bitops_h */
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
Code Review / vpp.git / blobdiff