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 <stdint.h>
40 #include <stdlib.h>
41 #include <stdio.h>
42
43 long long int
rand_long_long(void)44 rand_long_long(void)
45 {
46 unsigned long long int r = 0;
47 size_t x;
48
49 for (x = 0; x < sizeof(r) / 4; x++)
50 r = (r << 32) | (lrand48() & 0xffffffffL);
51 return r;
52 }
53
54 int
slow_ffs(int i)55 slow_ffs(int i)
56 {
57 int p;
58 if (!i)
59 return 0;
60 for (p = 1; (i & (1 << (p - 1))) == 0; p++)
61 ;
62 return p;
63 }
64
65 int
slow_ffsl(long int i)66 slow_ffsl(long int i)
67 {
68 int p;
69 if (!i)
70 return 0;
71 for (p = 1; (i & (1L << (p - 1))) == 0; p++)
72 ;
73 return p;
74 }
75
76 int
slow_ffsll(long long int i)77 slow_ffsll(long long int i)
78 {
79 int p;
80 if (!i)
81 return 0;
82 for (p = 1; (i & (1LL << (p - 1))) == 0; p++)
83 ;
84 return p;
85 }
86
87 static int
check(long long int x,int got,int expect,char * which)88 check(long long int x, int got, int expect, char *which)
89 {
90 long int low = x & 0xffffffffl;
91 long int high = ((x >> 16) >> 16) & 0xffffffffl;
92 if (got != expect) {
93 printf("failed %s(%08lx%08lx): got %d expect %d\n", which, high, low, got, expect);
94 return 1;
95 }
96 return 0;
97 }
98
99 int
main(void)100 main(void)
101 {
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 (size_t 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 (int32_t 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
