Mercurial > hg > octave-kai > gnulib-hg
annotate lib/ffs.c @ 17342:c75939cb6254
merge with default branch
| author | Michael Goffioul <michael.goffioul@gmail.com> |
|---|---|
| date | Thu, 21 Feb 2013 14:57:31 +0000 |
| parents | e542fd46ad6f |
| children |
| rev | line source |
|---|---|
| 15390 | 1 /* ffs.c -- find the first set bit in a word. |
|
17249
e542fd46ad6f
maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents:
16201
diff
changeset
|
2 Copyright (C) 2011-2013 Free Software Foundation, Inc. |
| 15390 | 3 |
| 4 This program is free software: you can redistribute it and/or modify | |
| 5 it under the terms of the GNU General Public License as published by | |
| 6 the Free Software Foundation; either version 3 of the License, or | |
| 7 (at your option) any later version. | |
| 8 | |
| 9 This program is distributed in the hope that it will be useful, | |
| 10 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 12 GNU General Public License for more details. | |
| 13 | |
| 14 You should have received a copy of the GNU General Public License | |
| 15 along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
| 16 | |
| 17 /* Written by Eric Blake. */ | |
| 18 | |
|
15945
f914ec364e88
ffs, bcopy, memset: Support symbol renaming via config.h.
Bruno Haible <bruno@clisp.org>
parents:
15426
diff
changeset
|
19 #include <config.h> |
|
f914ec364e88
ffs, bcopy, memset: Support symbol renaming via config.h.
Bruno Haible <bruno@clisp.org>
parents:
15426
diff
changeset
|
20 |
|
f914ec364e88
ffs, bcopy, memset: Support symbol renaming via config.h.
Bruno Haible <bruno@clisp.org>
parents:
15426
diff
changeset
|
21 /* Specification. */ |
| 15390 | 22 #include <strings.h> |
| 23 | |
|
15426
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
24 #include <limits.h> |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
25 |
| 15390 | 26 int |
| 27 ffs (int i) | |
| 28 { | |
| 29 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) | |
| 30 return __builtin_ffs (i); | |
| 31 #else | |
| 32 /* http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup | |
| 33 gives this deBruijn constant for a branch-less computation, although | |
|
15426
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
34 that table counted trailing zeros rather than bit position. This |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
35 requires 32-bit int, we fall back to a naive algorithm on the rare |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
36 platforms where that assumption is not true. */ |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
37 if (CHAR_BIT * sizeof i == 32) |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
38 { |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
39 static unsigned int table[] = { |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
40 1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
41 32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10 |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
42 }; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
43 unsigned int u = i; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
44 unsigned int bit = u & -u; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
45 return table[(bit * 0x077cb531U) >> 27] - !i; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
46 } |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
47 else |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
48 { |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
49 unsigned int j; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
50 for (j = 0; j < CHAR_BIT * sizeof i; j++) |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
51 if (i & (1U << j)) |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
52 return j + 1; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
53 return 0; |
|
60c6b6da0198
ffs: avoid undefined behavior
Eric Blake <eblake@redhat.com>
parents:
15390
diff
changeset
|
54 } |
| 15390 | 55 #endif |
| 56 } |