1 // SPDX-License-Identifier: GPL-2.0-only
3  * KUnit tests for ffs()-family functions
13 	int expected_ffs;	/* ffs() result (1-based) */
14 	int expected_fls;	/* fls() result (1-based) */
20 	int expected_fls64;		    /* fls64() result (1-based) */
21 	unsigned int expected_ffs64_0based; /* __ffs64() result (0-based) */
26  * Basic edge cases - core functionality validation
29 	/* Zero case - special handling */
32 	/* Single bit patterns - powers of 2 */
33 	{0x00000001, 1, 1, "bit 0 set"},
34 	{0x00000002, 2, 2, "bit 1 set"},
35 	{0x00000004, 3, 3, "bit 2 set"},
36 	{0x00000008, 4, 4, "bit 3 set"},
37 	{0x00000010, 5, 5, "bit 4 set"},
38 	{0x00000020, 6, 6, "bit 5 set"},
39 	{0x00000040, 7, 7, "bit 6 set"},
40 	{0x00000080, 8, 8, "bit 7 set"},
41 	{0x00000100, 9, 9, "bit 8 set"},
42 	{0x00008000, 16, 16, "bit 15 set"},
43 	{0x00010000, 17, 17, "bit 16 set"},
44 	{0x40000000, 31, 31, "bit 30 set"},
45 	{0x80000000, 32, 32, "bit 31 set (sign bit)"},
50 	/* Multiple bit patterns */
51 	{0x00000003, 1, 2, "bits 0-1 set"},
52 	{0x00000007, 1, 3, "bits 0-2 set"},
53 	{0x0000000F, 1, 4, "bits 0-3 set"},
54 	{0x000000FF, 1, 8, "bits 0-7 set"},
55 	{0x0000FFFF, 1, 16, "bits 0-15 set"},
56 	{0x7FFFFFFF, 1, 31, "bits 0-30 set"},
66  * 64-bit test cases
72 	/* Single bit patterns */
73 	{0x0000000000000001ULL, 1, 0, "bit 0 set"},
74 	{0x0000000000000002ULL, 2, 1, "bit 1 set"},
75 	{0x0000000000000004ULL, 3, 2, "bit 2 set"},
76 	{0x0000000000000008ULL, 4, 3, "bit 3 set"},
77 	{0x0000000000008000ULL, 16, 15, "bit 15 set"},
78 	{0x0000000000010000ULL, 17, 16, "bit 16 set"},
79 	{0x0000000080000000ULL, 32, 31, "bit 31 set"},
80 	{0x0000000100000000ULL, 33, 32, "bit 32 set"},
81 	{0x0000000200000000ULL, 34, 33, "bit 33 set"},
82 	{0x4000000000000000ULL, 63, 62, "bit 62 set"},
83 	{0x8000000000000000ULL, 64, 63, "bit 63 set (sign bit)"},
86 	{0xFFFFFFFFFFFFFFFFULL, 64, 0, "all bits set"},
88 	/* Cross 32-bit boundary patterns */
90 	{0xFFFFFFFF00000000ULL, 64, 32, "upper 32 bits set"},
91 	{0x8000000000000001ULL, 64, 0, "bits 0,63 set"},
95 	{0x00000001FFFFFFFFULL, 33, 0, "bit 32 + lower 32 bits"},
96 	{0xFFFFFFFF80000000ULL, 64, 31, "upper 32 bits + bit 31"},
112  * Helper function to validate 64-bit ffs results
164  * Helper function to validate 64-bit relationships
181 	KUNIT_EXPECT_LE(test, fls64_result, 64);  in validate_ffs64_relationships()
182 	KUNIT_EXPECT_LT(test, ffs64_0based, 64);  in validate_ffs64_relationships()
185 	 * Relationships with 32-bit functions should hold for small values  in validate_ffs64_relationships()
205  * Test basic correctness of all ffs-family functions
215 		validate_ffs_result(test, tc->input, ffs(tc->input),  in ffs_basic_correctness_test()
216 				    tc->expected_ffs, "ffs", tc->description);  in ffs_basic_correctness_test()
219 		validate_ffs_result(test, tc->input, fls(tc->input),  in ffs_basic_correctness_test()
220 				    tc->expected_fls, "fls", tc->description);  in ffs_basic_correctness_test()
222 		/* Test __ffs() - skip zero case as it's undefined */  in ffs_basic_correctness_test()
223 		if (tc->input != 0) {  in ffs_basic_correctness_test()
224 			/* Calculate expected __ffs() result: __ffs(x) == ffs(x) - 1 */  in ffs_basic_correctness_test()
225 			unsigned int expected_ffs_0based = tc->expected_ffs - 1;  in ffs_basic_correctness_test()
226 			validate_ffs_result(test, tc->input, __ffs(tc->input),  in ffs_basic_correctness_test()
227 					    expected_ffs_0based, "__ffs", tc->description);  in ffs_basic_correctness_test()
230 		/* Test __fls() - skip zero case as it's undefined */  in ffs_basic_correctness_test()
231 		if (tc->input != 0) {  in ffs_basic_correctness_test()
232 			/* Calculate expected __fls() result: __fls(x) == fls(x) - 1 */  in ffs_basic_correctness_test()
233 			unsigned int expected_fls_0based = tc->expected_fls - 1;  in ffs_basic_correctness_test()
234 			validate_ffs_result(test, tc->input, __fls(tc->input),  in ffs_basic_correctness_test()
235 					    expected_fls_0based, "__fls", tc->description);  in ffs_basic_correctness_test()
241  * Test 64-bit function correctness
251 		validate_ffs64_result(test, tc->input, fls64(tc->input),  in ffs64_correctness_test()
252 				      tc->expected_fls64, "fls64", tc->description);  in ffs64_correctness_test()
254 		/* Test __ffs64() - skip zero case as it's undefined */  in ffs64_correctness_test()
255 		if (tc->input != 0) {  in ffs64_correctness_test()
256 			validate_ffs64_result(test, tc->input, __ffs64(tc->input),  in ffs64_correctness_test()
257 					      tc->expected_ffs64_0based, "__ffs64",  in ffs64_correctness_test()
258 					      tc->description);  in ffs64_correctness_test()
275 	/* Test 64-bit cases */  in ffs_mathematical_relationships_test()
288 		1UL, 2UL, 4UL, 8UL, 16UL, 32UL, 64UL, 128UL,  in ffs_edge_cases_test()
296 		0x7FFFFFFFUL,	/* Maximum positive 32-bit */  in ffs_edge_cases_test()
297 		0x80000000UL,	/* Minimum negative 32-bit */  in ffs_edge_cases_test()
298 		0xFFFFFFFFUL,	/* Maximum 32-bit unsigned */  in ffs_edge_cases_test()
308  * Test 64-bit edge cases
313 		/* 64-bit powers of 2 */  in ffs64_edge_cases_test()
324 		/* Cross-boundary patterns */  in ffs64_edge_cases_test()
327 		0x7FFFFFFFFFFFFFFFULL,	/* Maximum positive 64-bit */  in ffs64_edge_cases_test()
328 		0xFFFFFFFFFFFFFFFFULL,	/* Maximum 64-bit unsigned */  in ffs64_edge_cases_test()
338  * ffz() test data - Find First Zero bit test cases
348 	{0xFFFFFFFE, 0, "bit 0 is zero"},      /* ...11111110 */
349 	{0xFFFFFFFD, 1, "bit 1 is zero"},      /* ...11111101 */
350 	{0xFFFFFFFB, 2, "bit 2 is zero"},      /* ...11111011 */
351 	{0xFFFFFFF7, 3, "bit 3 is zero"},      /* ...11110111 */
352 	{0xFFFFFFEF, 4, "bit 4 is zero"},      /* ...11101111 */
353 	{0xFFFFFFDF, 5, "bit 5 is zero"},      /* ...11011111 */
354 	{0xFFFFFFBF, 6, "bit 6 is zero"},      /* ...10111111 */
355 	{0xFFFFFF7F, 7, "bit 7 is zero"},      /* ...01111111 */
356 	{0xFFFFFEFF, 8, "bit 8 is zero"},      /* Gap in bit 8 */
357 	{0xFFFF7FFF, 15, "bit 15 is zero"},    /* Gap in bit 15 */
358 	{0xFFFEFFFF, 16, "bit 16 is zero"},    /* Gap in bit 16 */
359 	{0xBFFFFFFF, 30, "bit 30 is zero"},    /* Gap in bit 30 */
360 	{0x7FFFFFFF, 31, "bit 31 is zero"},    /* 01111111... */
363 	{0xFFFFFFFC, 0, "bits 0-1 are zero"},  /* ...11111100 */
364 	{0xFFFFFFF8, 0, "bits 0-2 are zero"},  /* ...11111000 */
365 	{0xFFFFFFF0, 0, "bits 0-3 are zero"},  /* ...11110000 */
366 	{0xFFFFFF00, 0, "bits 0-7 are zero"},  /* ...00000000 */
367 	{0xFFFF0000, 0, "bits 0-15 are zero"}, /* Lower 16 bits zero */
373 	{0xFFFDFFFF, 17, "bit 17 is zero"},    /* Gap in bit 17 */
374 	{0xFFF7FFFF, 19, "bit 19 is zero"},    /* Gap in bit 19 */
375 	{0xF7FFFFFF, 27, "bit 27 is zero"},    /* Gap in bit 27 */
376 	{0xDFFFFFFF, 29, "bit 29 is zero"},    /* Gap in bit 29 */
388 		unsigned long result = ffz(tc->input);  in ffz_basic_correctness_test()
390 		KUNIT_EXPECT_EQ_MSG(test, result, tc->expected_ffz,  in ffz_basic_correctness_test()
392 				    tc->input, tc->description, tc->expected_ffz, result);  in ffz_basic_correctness_test()
404 		/* ffz(0) should return 0 (first zero bit is at position 0) */  in validate_ffz_relationships()
410 		/* ffz(~0) is undefined (no zero bits) - just verify it doesn't crash */  in validate_ffz_relationships()
412 		/* Implementation-defined behavior, just ensure it completes */  in validate_ffz_relationships()
418 	/* Range validation - result should be within valid bit range */  in validate_ffz_relationships()
421 	/* Verify the bit at ffz_result position is actually zero */  in validate_ffz_relationships()
423 			    "ffz(0x%08lx) = %lu, but bit %lu is not zero",  in validate_ffz_relationships()
426 	/* Core relationship: if we set the ffz bit, ffz should find a different bit */  in validate_ffz_relationships()
427 	if (ffz_result < BITS_PER_LONG - 1) {  in validate_ffz_relationships()
432 					    "ffz(0x%08lx) = %lu, but setting that bit doesn't change ffz result",  in validate_ffz_relationships()
441 		/* Powers of 2 with one bit clear */  in ffz_mathematical_relationships_test()
449 		/* Complex bit patterns */  in ffz_mathematical_relationships_test()
479 		/* Powers of 2 complement patterns (one zero bit each) */  in ffz_edge_cases_test()
565 MODULE_DESCRIPTION("KUnit tests for ffs()-family functions");