A modern Music Player Daemon based on Rockbox open source high quality audio player
tsiry-sandratraina.com
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/***************************************************************************
2 * __________ __ ___.
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
7 * \/ \/ \/ \/ \/
8 * $Id$
9 *
10 * Copyright (C) 2014 by Michael Sevakis
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
16 *
17 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
18 * KIND, either express or implied.
19 *
20 ****************************************************************************/
21#ifndef BITARRAY_H
22#define BITARRAY_H
23
24/* Type-checked bit array definitions */
25
26/* All this stuff gets optimized into very simple object code */
27
28#define BITARRAY_WORD_BITS \
29 (sizeof (unsigned int) * 8)
30#define BITARRAY_NWORDS(bits) \
31 (((bits) + BITARRAY_WORD_BITS - 1) / BITARRAY_WORD_BITS)
32#define BITARRAY_BITWORD(bitnum) \
33 ((bitnum) / BITARRAY_WORD_BITS)
34#define BITARRAY_WORDBIT(bitnum) \
35 ((bitnum) % BITARRAY_WORD_BITS)
36#define BITARRAY_NBIT(word, bit) \
37 ((word)*BITARRAY_WORD_BITS + (bit))
38#define BITARRAY_BITS(bits) \
39 (BITARRAY_NWORDS(bits)*BITARRAY_WORD_BITS)
40#define BITARRAY_BITN(bitnum) \
41 (1u << BITARRAY_WORDBIT(bitnum))
42
43
44/** Iterators **/
45#include "config.h"
46#include <stdint.h>
47#include <limits.h>
48
49#if (defined(CPU_ARM) && ARM_ARCH >= 5) || UINT32_MAX < UINT_MAX
50#define __BITARRAY_CTZ(wval) __builtin_ctz(wval)
51#else
52#include "system.h"
53#define __BITARRAY_CTZ(wval) find_first_set_bit(wval)
54#endif
55#define __BITARRAY_POPCNT(wval) __builtin_popcount(wval)
56
57#ifndef BIT_N
58#define BIT_N(n) (1u << (n))
59#endif
60
61/* Enumerate each word index */
62#define FOR_EACH_BITARRAY_WORD_INDEX(nwords, index) \
63 for (unsigned int index = 0, _nwords = (nwords); \
64 index < _nwords; index++)
65
66/* Enumerate each word value */
67#define FOR_EACH_BITARRAY_WORD(a, wval) \
68 FOR_EACH_BITARRAY_WORD_INDEX(ARRAYLEN((a)->words), _w) \
69 for (unsigned int wval = (a)->words[_w], _ = 1; _; _--)
70
71/* Enumerate the bit number of each set bit of a word in sequence */
72#define FOR_EACH_BITARRAY_SET_WORD_BIT(wval, bit) \
73 for (unsigned int _wval = (wval), bit; \
74 _wval ? (((bit) = __BITARRAY_CTZ(_wval)), 1) : 0; \
75 _wval &= ~BIT_N(bit))
76
77/* Enumerate the bit number of each set bit in the bit array in sequence */
78#define FOR_EACH_BITARRAY_SET_BIT_ARR(nwords, words, nbit) \
79 FOR_EACH_BITARRAY_WORD_INDEX(nwords, _w) \
80 FOR_EACH_BITARRAY_SET_WORD_BIT(words[_w], _bit) \
81 for (unsigned int nbit = BITARRAY_NBIT(_w, _bit), _ = 1; _; _--)
82
83/* As above but takes an array type for an argument */
84#define FOR_EACH_BITARRAY_SET_BIT(a, nbit) \
85 FOR_EACH_BITARRAY_SET_BIT_ARR(ARRAYLEN((a)->words), (a)->words, nbit)
86
87
88/** Base functions (called by typed functions) **/
89
90/* Return the word associated with the bit */
91static inline unsigned int
92__bitarray_get_word(unsigned int words[], unsigned int bitnum)
93{
94 return words[BITARRAY_BITWORD(bitnum)];
95}
96
97/* Set the word associated with the bit */
98static inline void
99__bitarray_set_word(unsigned int words[], unsigned int bitnum,
100 unsigned int wordval)
101{
102 words[BITARRAY_BITWORD(bitnum)] = wordval;
103}
104
105/* Set the bit at index 'bitnum' to '1' */
106static inline void
107__bitarray_set_bit(unsigned int words[], unsigned int bitnum)
108{
109 unsigned int word = BITARRAY_BITWORD(bitnum);
110 unsigned int bit = BITARRAY_BITN(bitnum);
111 words[word] |= bit;
112}
113
114/* Set the bit at index 'bitnum' to '0' */
115static inline void
116__bitarray_clear_bit(unsigned int words[], unsigned int bitnum)
117{
118 unsigned int word = BITARRAY_BITWORD(bitnum);
119 unsigned int bit = BITARRAY_BITN(bitnum);
120 words[word] &= ~bit;
121}
122
123/* Return the value of the specified bit ('0' or '1') */
124static inline unsigned int
125__bitarray_test_bit(const unsigned int words[], unsigned int bitnum)
126{
127 unsigned int word = BITARRAY_BITWORD(bitnum);
128 unsigned int nbit = BITARRAY_WORDBIT(bitnum);
129 return (words[word] >> nbit) & 1u;
130}
131
132/* Check if all bits in the bit array are '0' */
133static inline bool
134__bitarray_is_clear(const unsigned int words[], unsigned int nbits)
135{
136 FOR_EACH_BITARRAY_WORD_INDEX(BITARRAY_NWORDS(nbits), word)
137 {
138 if (words[word] != 0)
139 return false;
140 }
141
142 return true;
143}
144
145/* Set every bit in the array to '0' */
146static inline void
147__bitarray_clear(unsigned int words[], unsigned int nbits)
148{
149 FOR_EACH_BITARRAY_WORD_INDEX(BITARRAY_NWORDS(nbits), word)
150 words[word] = 0;
151}
152
153/* Set every bit in the array to '1' */
154static inline void
155__bitarray_set(unsigned int words[], unsigned int nbits)
156{
157 FOR_EACH_BITARRAY_WORD_INDEX(BITARRAY_NWORDS(nbits), word)
158 words[word] = ~0u;
159}
160
161/* Find the lowest-indexed '1' bit in the bit array, returning the size of
162 the array if none are set */
163static inline unsigned int
164__bitarray_ffs(const unsigned int words[], unsigned int nbits)
165{
166 FOR_EACH_BITARRAY_SET_BIT_ARR(BITARRAY_NWORDS(nbits), words, nbit)
167 return nbit;
168
169 return BITARRAY_BITS(nbits);
170}
171
172/* Return the number of bits currently set to '1' in the bit array */
173static inline unsigned int
174__bitarray_popcount(const unsigned int words[], unsigned int nbits)
175{
176 unsigned int count = 0;
177
178 FOR_EACH_BITARRAY_WORD_INDEX(BITARRAY_NWORDS(nbits), word)
179 count += __BITARRAY_POPCNT(words[word]);
180
181 return count;
182}
183
184/**
185 * Giant macro to define all the typed functions
186 * typename: The name of the type (e.g. myarr_t myarr;)
187 * fnprefix: The prefix all functions get (e.g. myarr_set_bit)
188 * nbits : The minimum number of bits the array is meant to hold
189 * (the implementation rounds this up to the word size
190 * and all words may be fully utilized)
191 *
192 * uses 'typedef' to freely change from, e.g., struct to union without
193 * changing source code
194 */
195#define BITARRAY_TYPE_DECLARE(typename, fnprefix, nbits) \
196typedef struct \
197{ \
198 unsigned int words[BITARRAY_NWORDS(nbits)]; \
199} typename; \
200static inline unsigned int \
201fnprefix##_get_word(typename *array, unsigned int bitnum) \
202 { return __bitarray_get_word(array->words, bitnum); } \
203static inline void \
204fnprefix##_set_word(typename *array, unsigned int bitnum, \
205 unsigned int wordval) \
206 { __bitarray_set_word(array->words, bitnum, wordval); } \
207static inline void \
208fnprefix##_set_bit(typename *array, unsigned int bitnum) \
209 { __bitarray_set_bit(array->words, bitnum); } \
210static inline void \
211fnprefix##_clear_bit(typename *array, unsigned int bitnum) \
212 { __bitarray_clear_bit(array->words, bitnum); } \
213static inline unsigned int \
214fnprefix##_test_bit(const typename *array, unsigned int bitnum) \
215 { return __bitarray_test_bit(array->words, bitnum); } \
216static inline bool \
217fnprefix##_is_clear(const typename *array) \
218 { return __bitarray_is_clear(array->words, nbits); } \
219static inline void \
220fnprefix##_clear(typename *array) \
221 { __bitarray_clear(array->words, nbits); } \
222static inline void \
223fnprefix##_set(typename *array) \
224 { __bitarray_set(array->words, nbits); } \
225static inline unsigned int \
226fnprefix##_ffs(const typename *array) \
227 { return __bitarray_ffs(array->words, nbits); } \
228static inline unsigned int \
229fnprefix##_popcount(const typename *array) \
230 { return __bitarray_popcount(array->words, nbits); }
231
232#endif /* BITARRAY_H */