| /* Simple and straight-forward malloc implementation (front end). | |
| Copyright (C) 2020-2026 Free Software Foundation, Inc. | |
| This file is free software: you can redistribute it and/or modify | |
| it under the terms of the GNU Lesser General Public License as | |
| published by the Free Software Foundation; either version 2.1 of the | |
| License, or (at your option) any later version. | |
| This file is distributed in the hope that it will be useful, | |
| but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| GNU Lesser General Public License for more details. | |
| You should have received a copy of the GNU Lesser General Public License | |
| along with this program. If not, see <https://www.gnu.org/licenses/>. */ | |
| /* Written by Bruno Haible <bruno@clisp.org>, 2020. */ | |
| /* ===================== Low-level functions for bitmaps ==================== */ | |
| /* A bitmap is represented as an array of uint32_t = 'unsigned int', each with | |
| 32 bits. The bit i in the word with index j therefore represents bit | |
| k = 32 * j + i of the entire bit sequence. */ | |
| /* Initializes a bitmap. */ | |
| static inline void | |
| init_bitmap_all_bits_clear (size_t num_words, uint32_t *words) | |
| { | |
| for (size_t i = 0; i < num_words; i++) | |
| words[i] = 0; | |
| } | |
| /* Initializes a bitmap. */ | |
| static inline void | |
| init_bitmap_all_bits_set (size_t num_words, uint32_t *words) | |
| { | |
| for (size_t i = 0; i < num_words; i++) | |
| words[i] = ~(uint32_t)0; | |
| } | |
| /* Returns the smallest index k >= k0 for which the bit k is set in the bitmap | |
| consisting of num_words words. Returns (size_t)(-1) if there is none. */ | |
| static size_t | |
| find_first_bit_set (size_t num_words, const uint32_t *words, size_t k0) | |
| { | |
| size_t j0 = k0 / 32; | |
| if (j0 < num_words) | |
| { | |
| size_t i0 = k0 % 32; | |
| const uint32_t *ptr = words + j0; | |
| /* Look at the word j0, ignoring the i0 least significant bits. */ | |
| { | |
| size_t found = ffs (*ptr & (-1U << i0)); | |
| if (found > 0) | |
| return 32 * j0 + (found - 1); | |
| } | |
| /* Look at the subsequent words. */ | |
| const uint32_t *words_end = words + num_words; | |
| while (++ptr < words_end) | |
| { | |
| size_t found = ffs (*ptr); | |
| if (found > 0) | |
| return 32 * (ptr - words) + (found - 1); | |
| } | |
| } | |
| return (size_t)(-1); | |
| } | |
| /* Returns the smallest index k >= 0 for which the bit packet of c consecutive | |
| bits (1 <= c <= 32) is all set in the bitmap consisting of num_words words. | |
| Returns (size_t)(-1) if there is none. */ | |
| static size_t | |
| find_first_packet_set (size_t num_words, const uint32_t *words, size_t c) | |
| { | |
| const uint32_t *ptr = words; | |
| const uint32_t *words_end = words + num_words; | |
| switch (c) | |
| { | |
| case 1: | |
| { | |
| /* A simplified variant of find_first_bit_set. */ | |
| for (; ptr < words_end; ptr++) | |
| { | |
| size_t found = ffs (*ptr); | |
| if (found > 0) | |
| return 32 * (ptr - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 2: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t combined = longword & (longword >> 1); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 3: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t combined = longword & (longword >> 1) & (longword >> 2); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 4: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t combined = tmp1 & (tmp1 >> 2); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 5: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t combined = tmp2 & (longword >> 4); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 6: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t combined = tmp1 & (tmp1 >> 2) & (tmp1 >> 4); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 7: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t combined = | |
| tmp1 & (tmp1 >> 2) & (tmp1 >> 4) & (longword >> 6); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 8: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t combined = tmp2 & (tmp2 >> 4); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 9: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = tmp3 & (longword >> 8); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 10: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = tmp3 & (tmp1 >> 8); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 11: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = tmp3 & (tmp1 >> 8) & (longword >> 10); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 12: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t combined = tmp2 & (tmp2 >> 4) & (tmp2 >> 8); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 13: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t combined = | |
| tmp2 & (tmp2 >> 4) & (tmp2 >> 8) & (longword >> 12); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 14: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t combined = tmp2 & (tmp2 >> 4) & (tmp2 >> 8) & (tmp1 >> 12); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 15: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| /* Optimized: Use 5, not 6, '&' operations. */ | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (longword >> 4); | |
| uint64_t combined = tmp3 & (tmp3 >> 5) & (tmp3 >> 10); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 16: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = tmp3 & (tmp3 >> 8); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 17: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (longword >> 16); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 18: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (tmp1 >> 16); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 19: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (tmp1 >> 16) & (longword >> 18); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 20: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (tmp2 >> 16); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 21: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (tmp2 >> 16) & (longword >> 20); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 22: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (tmp2 >> 16) & (tmp1 >> 20); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 23: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = | |
| tmp4 & (tmp2 >> 16) & (tmp1 >> 20) & (longword >> 22); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 24: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = tmp3 & (tmp3 >> 8) & (tmp3 >> 16); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 25: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = | |
| tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (longword >> 24); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 26: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = | |
| tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp1 >> 24); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 27: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| /* Optimized: Use 6, not 7, '&' operations. */ | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (longword >> 8); | |
| uint64_t combined = tmp4 & (tmp4 >> 9) & (tmp4 >> 18); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 28: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = | |
| tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp2 >> 24); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 29: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t combined = | |
| tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp2 >> 24) & (longword >> 28); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 30: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| /* Optimized: Use 6, not 7, '&' operations. */ | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp1 >> 8); | |
| uint64_t combined = tmp4 & (tmp4 >> 10) & (tmp4 >> 20); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 31: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = | |
| tmp4 & (tmp3 >> 16) & (tmp2 >> 24) & (tmp1 >> 28) & (longword >> 30); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| case 32: | |
| { | |
| while (ptr < words_end) | |
| { | |
| uint64_t longword = *ptr++; | |
| if (likely (ptr < words_end)) | |
| longword |= ((uint64_t) *ptr) << 32; | |
| uint64_t tmp1 = longword & (longword >> 1); | |
| uint64_t tmp2 = tmp1 & (tmp1 >> 2); | |
| uint64_t tmp3 = tmp2 & (tmp2 >> 4); | |
| uint64_t tmp4 = tmp3 & (tmp3 >> 8); | |
| uint64_t combined = tmp4 & (tmp4 >> 16); | |
| size_t found = ffsll (combined); | |
| if (found > 0) | |
| return 32 * (ptr - 1 - words) + (found - 1); | |
| } | |
| return (size_t)(-1); | |
| } | |
| default: | |
| /* Invalid argument. */ | |
| abort (); | |
| } | |
| } |