1 /*
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright © 2020 Keith Packard
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 *
18 * 3. Neither the name of the copyright holder nor the names of its
19 * contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
27 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
28 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
29 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
31 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
33 * OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #define _DEFAULT_SOURCE
37 #include <strings.h>
38 #include <string.h>
39 #include <stdlib.h>
40 #include <stdio.h>
41
42 long long int
rand_long_long(void)43 rand_long_long(void)
44 {
45 unsigned long long int r = 0;
46 size_t x;
47
48 for (x = 0; x < sizeof(r) / 4; x++)
49 r = (r << 32) | (lrand48() & 0xffffffffL);
50 return r;
51 }
52
53 int
slow_ffs(int i)54 slow_ffs(int i)
55 {
56 int p;
57 if (!i)
58 return 0;
59 for (p = 1; (i & (1 << (p - 1))) == 0; p++)
60 ;
61 return p;
62 }
63
64 int
slow_ffsl(long int i)65 slow_ffsl(long int i)
66 {
67 int p;
68 if (!i)
69 return 0;
70 for (p = 1; (i & (1L << (p - 1))) == 0; p++)
71 ;
72 return p;
73 }
74
75 int
slow_ffsll(long long int i)76 slow_ffsll(long long int i)
77 {
78 int p;
79 if (!i)
80 return 0;
81 for (p = 1; (i & (1LL << (p - 1))) == 0; p++)
82 ;
83 return p;
84 }
85
86 static int
check(long long int x,int got,int expect,char * which)87 check(long long int x, int got, int expect, char *which)
88 {
89 long int low = x & 0xffffffffl;
90 long int high = ((x >> 16) >> 16) & 0xffffffffl;
91 if (got != expect) {
92 printf("failed %s(%08lx%08lx): got %d expect %d\n", which, high, low, got, expect);
93 return 1;
94 }
95 return 0;
96 }
97
98 int
main(void)99 main(void)
100 {
101 size_t i;
102 int ret = 0;
103
104 /* Test zero */
105 ret += check(0, ffs(0), slow_ffs(0), "ffs");
106 ret += check(0, ffsl(0), slow_ffsl(0), "ffsl");
107 ret += check(0, ffsll(0), slow_ffsll(0), "ffsll");
108
109 /* Test every bit position in a long long */
110 for (i = 0; i < sizeof(long long) * 8; i++) {
111 long long int xll = 1LL << i;
112 long xl = (long) xll;
113 int x = (int) xll;
114
115 ret += check(x, ffs(x), slow_ffs(x), "ffs");
116 ret += check(xl, ffsl(xl), slow_ffsl(xl), "ffsl");
117 ret += check(xll, ffsll(xll), slow_ffsll(xll), "ffsll");
118 }
119
120 /* Test another few random values */
121 #define N 100000
122 for (i = 0; i < N; i++) {
123 long long int xll = rand_long_long();
124 long xl = (long) xll;
125 int x = (int) xll;
126
127 ret += check(x, ffs(x), slow_ffs(x), "ffs");
128 ret += check(xl, ffsl(xl), slow_ffsl(xl), "ffsl");
129 ret += check(xll, ffsll(xll), slow_ffsll(xll), "ffsll");
130 }
131 return ret;
132 }
133
