4 * This file is part of BeRTOS.
6 * Bertos is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * As a special exception, you may use this file as part of a free software
21 * library without restriction. Specifically, if other files instantiate
22 * templates or use macros or inline functions from this file, or you compile
23 * this file and link it with other files to produce an executable, this
24 * file does not by itself cause the resulting executable to be covered by
25 * the GNU General Public License. This exception does not however
26 * invalidate any other reasons why the executable file might be covered by
27 * the GNU General Public License.
29 * Copyright 2011 Develer S.r.l. (http://www.develer.com/)
32 * \brief Bitarray module
34 * \author Daniele Basile <asterix@develer.com>
42 // De Bruijn constant coefficents.
43 static const uint8_t DeBruijn_coefficents[32] =
45 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
46 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
50 * Return the position of the first bit non zero in bitarray
52 * \param bitx BitArray context
53 * \return Position in bitarray when firt bit non zero occur, -1 otherwise
55 int bitarray_firstSetBit(BitArray *bitx)
59 uint8_t *b = bitx->array;
60 size_t bytes = bitx->size;
66 size_t len = MIN(bytes, (size_t)4);
67 memcpy(&data, b, len);
70 return (DeBruijn_coefficents[((uint32_t)((data & -data) * 0x077CB531U)) >> 27] + curr);