Mercurial > gnulib

annotate lib/ffsl.h @ 40186:8964917f9574

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
autoupdate
author Karl Berry <karl@freefriends.org>
date Mon, 18 Feb 2019 08:02:49 -0800
parents b06060465f09
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
1 /* ffsl.h -- find the first set bit in a word.
40057
b06060465f09 maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents: 19484
diff changeset
2 Copyright (C) 2011-2019 Free Software Foundation, Inc.
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
3
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
4 This program is free software: you can redistribute it and/or modify
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
5 it under the terms of the GNU General Public License as published by
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
6 the Free Software Foundation; either version 3 of the License, or
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
7 (at your option) any later version.
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
8
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
9 This program is distributed in the hope that it will be useful,
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
12 GNU General Public License for more details.
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
13
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
14 You should have received a copy of the GNU General Public License
19190
9759915b2aca all: prefer https: URLs
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
16
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
17 /* Written by Eric Blake. */
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
18
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
19 /* This file is meant to be included by ffsl.c and ffsll.c, after
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
20 they have defined FUNC and TYPE. */
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
21
16007
d057d14ac3bb ffsl, ffsll: Avoid compilation error due to 'restrict'.
Bruno Haible <bruno@clisp.org>
parents: 15949
diff changeset
22 #include <config.h>
d057d14ac3bb ffsl, ffsll: Avoid compilation error due to 'restrict'.
Bruno Haible <bruno@clisp.org>
parents: 15949
diff changeset
23
d057d14ac3bb ffsl, ffsll: Avoid compilation error due to 'restrict'.
Bruno Haible <bruno@clisp.org>
parents: 15949
diff changeset
24 /* Specification. */
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
25 #include <string.h>
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
26
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
27 #include <limits.h>
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
28 #include <strings.h>
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
29
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
30 #if !defined FUNC || !defined TYPE
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
31 # error
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
32 #endif
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
33
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
34 int
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
35 FUNC (TYPE i)
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
36 {
15946
d0eb709725f5 ffsl, ffsll: Optimize for GCC.
Bruno Haible <bruno@clisp.org>
parents: 15430
diff changeset
37 #if (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && defined GCC_BUILTIN
d0eb709725f5 ffsl, ffsll: Optimize for GCC.
Bruno Haible <bruno@clisp.org>
parents: 15430
diff changeset
38 return GCC_BUILTIN (i);
d0eb709725f5 ffsl, ffsll: Optimize for GCC.
Bruno Haible <bruno@clisp.org>
parents: 15430
diff changeset
39 #else
15949
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
40 unsigned TYPE j = i;
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
41 /* Split j into chunks, and look at one chunk after the other. */
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
42 enum { chunk_bits = CHAR_BIT * sizeof (unsigned int) };
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
43 /* The number of chunks is ceil (sizeof (TYPE) / sizeof (unsigned int))
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
44 = (sizeof (TYPE) - 1) / sizeof (unsigned int) + 1. */
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
45 enum { chunk_count = (sizeof (TYPE) - 1) / sizeof (unsigned int) + 1 };
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
46
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
47 if (chunk_count > 1)
15947
d1ff4390df13 ffsl: Optimize on 32-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15946
diff changeset
48 {
15949
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
49 size_t k;
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
50
15947
d1ff4390df13 ffsl: Optimize on 32-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15946
diff changeset
51 /* It is tempting to write if (!j) here, but if we do this,
d1ff4390df13 ffsl: Optimize on 32-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15946
diff changeset
52 Solaris 10/x86 "cc -O" miscompiles the code. */
d1ff4390df13 ffsl: Optimize on 32-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15946
diff changeset
53 if (!i)
d1ff4390df13 ffsl: Optimize on 32-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15946
diff changeset
54 return 0;
15949
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
55 /* Unroll the first loop round. k = 0. */
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
56 if ((unsigned int) j)
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
57 return ffs ((unsigned int) j);
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
58 /* Generic loop. */
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
59 for (k = 1; k < chunk_count - 1; k++)
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
60 if ((unsigned int) (j >> (k * chunk_bits)) != 0)
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
61 return k * chunk_bits + ffs ((unsigned int) (j >> (k * chunk_bits)));
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
62 }
15949
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
63 /* Last loop round. k = chunk_count - 1. */
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
64 return (chunk_count - 1) * chunk_bits
0319356f65c3 ffsl: Optimize on 64-bit platforms.
Bruno Haible <bruno@clisp.org>
parents: 15947
diff changeset
65 + ffs ((unsigned int) (j >> ((chunk_count - 1) * chunk_bits)));
15946
d0eb709725f5 ffsl, ffsll: Optimize for GCC.
Bruno Haible <bruno@clisp.org>
parents: 15430
diff changeset
66 #endif
15428
4e3a37b1ceae ffsl, ffsll: new modules
Eric Blake <eblake@redhat.com>
parents:
diff changeset
67 }