1 #ifndef IWBITS_H
2 #define IWBITS_H
3
4 //
5 /**************************************************************************************************
6 * IOWOW library
7 *
8 * MIT License
9 *
10 * Copyright (c) 2012-2020 Softmotions Ltd <info@softmotions.com>
11 *
12 * Permission is hereby granted, free of charge, to any person obtaining a copy
13 * of this software and associated documentation files (the "Software"), to deal
14 * in the Software without restriction, including without limitation the rights
15 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 * copies of the Software, and to permit persons to whom the Software is
17 * furnished to do so, subject to the following conditions:
18 *
19 * The above copyright notice and this permission notice shall be included in all
20 * copies or substantial portions of the Software.
21 *
22 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28 * SOFTWARE.
29 *************************************************************************************************/
30
31
32 /** @file
33 * @brief Various bit manipulation utility methods.
34 */
35
36 #include "basedefs.h"
37 #include <stdint.h>
38
39 IW_EXTERN_C_START
40
41 #if defined(__GNUC__) || defined(__clang__)
42 #pragma GCC diagnostic push
43 #pragma GCC diagnostic ignored "-Wlong-long"
44 #endif
45
46 /**
47 * @brief Find the first set bit number. Undefined if @a x is zero.
48 */
iwbits_find_first_sbit64(uint64_t x)49 IW_INLINE uint8_t iwbits_find_first_sbit64(uint64_t x) {
50 //return __builtin_ffsll(x) - 1;
51 uint8_t ret = 0;
52 if ((x & 0xffffffffU) == 0) {
53 ret += 32;
54 x >>= 32;
55 }
56 if ((x & 0xffffU) == 0) {
57 ret += 16;
58 x >>= 16;
59 }
60 if ((x & 0xffU) == 0) {
61 ret += 8;
62 x >>= 8;
63 }
64 if ((x & 0xfU) == 0) {
65 ret += 4;
66 x >>= 4;
67 }
68 if ((x & 0x3U) == 0) {
69 ret += 2;
70 x >>= 2;
71 }
72 if ((x & 0x1U) == 0) {
73 ret += 1;
74 }
75 return ret;
76 }
77
78 /**
79 * @brief Find the last set bit number. Undefined if @a x is zero.
80 */
iwbits_find_last_sbit64(uint64_t x)81 IW_INLINE uint8_t iwbits_find_last_sbit64(uint64_t x) {
82 //return 63 - __builtin_clzll(x);
83 uint8_t num = 63;
84 if ((x & 0xffffffff00000000ULL) == 0) {
85 num -= 32;
86 x <<= 32;
87 }
88 if ((x & 0xffff000000000000ULL) == 0) {
89 num -= 16;
90 x <<= 16;
91 }
92 if ((x & 0xff00000000000000ULL) == 0) {
93 num -= 8;
94 x <<= 8;
95 }
96 if ((x & 0xf000000000000000ULL) == 0) {
97 num -= 4;
98 x <<= 4;
99 }
100 if ((x & 0xc000000000000000ULL) == 0) {
101 num -= 2;
102 x <<= 2;
103 }
104 if ((x & 0x8000000000000000ULL) == 0) {
105 num -= 1;
106 }
107 return num;
108 }
109
110 /**
111 * @brief Reverese bits in a given @a x
112 * Thanks to: http://www.hackersdelight.org/hdcodetxt/reverse.c.txt
113 */
iwbits_reverse_64(uint64_t x)114 IW_INLINE uint64_t iwbits_reverse_64(uint64_t x) {
115 uint64_t t;
116 x = (x << 32) | (x >> 32); /* Swap register halves. */
117 x = (x & 0x0001ffff0001ffffLL) << 15 | /* Rotate left */
118 (x & 0xfffe0000fffe0000LL) >> 17; /* 15. */
119 t = (x ^ (x >> 10)) & 0x003f801f003f801fLL;
120 x = (t | (t << 10)) ^ x;
121 t = (x ^ (x >> 4)) & 0x0e0384210e038421LL;
122 x = (t | (t << 4)) ^ x;
123 t = (x ^ (x >> 2)) & 0x2248884222488842LL;
124 x = (t | (t << 2)) ^ x;
125 return x;
126 }
127
128 #if defined(__GNUC__) || defined(__clang__)
129 #pragma GCC diagnostic pop
130 #endif
131
132 IW_EXTERN_C_END
133 #endif
134