lib/ssfmalloc-bitmap.h

   1 /* Simple and straight-forward malloc implementation (front end).
   2
   3    Copyright (C) 2020-2024 Free Software Foundation, Inc.
   4
   5    This file is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU Lesser General Public License as
   7    published by the Free Software Foundation; either version 2.1 of the
   8    License, or (at your option) any later version.
   9
  10    This file is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* Written by Bruno Haible <bruno@clisp.org>, 2020.  */
  19
  20 /* ===================== Low-level functions for bitmaps ==================== */
  21
  22 /* A bitmap is represented as an array of uint32_t = 'unsigned int', each with
  23    32 bits.  The bit i in the word with index j therefore represents bit
  24    k = 32 * j + i of the entire bit sequence.  */
  25
  26 /* Initializes a bitmap.  */
  27 static inline void
  28 init_bitmap_all_bits_clear (size_t num_words, uint32_t *words)
  29 {
  30   size_t i;
  31   for (i = 0; i < num_words; i++)
  32     words[i] = 0;
  33 }
  34
  35 /* Initializes a bitmap.  */
  36 static inline void
  37 init_bitmap_all_bits_set (size_t num_words, uint32_t *words)
  38 {
  39   size_t i;
  40   for (i = 0; i < num_words; i++)
  41     words[i] = ~(uint32_t)0;
  42 }
  43
  44 /* Returns the smallest index k >= k0 for which the bit k is set in the bitmap
  45    consisting of num_words words.  Returns (size_t)(-1) if there is none.  */
  46 static size_t
  47 find_first_bit_set (size_t num_words, const uint32_t *words, size_t k0)
  48 {
  49   size_t j0 = k0 / 32;
  50   if (j0 < num_words)
  51     {
  52       size_t i0 = k0 % 32;
  53       const uint32_t *ptr = words + j0;
  54       /* Look at the word j0, ignoring the i0 least significant bits.  */
  55       {
  56         size_t found = ffs (*ptr & (-1U << i0));
  57         if (found > 0)
  58           return 32 * j0 + (found - 1);
  59       }
  60       /* Look at the subsequent words.  */
  61       const uint32_t *words_end = words + num_words;
  62       while (++ptr < words_end)
  63         {
  64           size_t found = ffs (*ptr);
  65           if (found > 0)
  66             return 32 * (ptr - words) + (found - 1);
  67         }
  68     }
  69   return (size_t)(-1);
  70 }
  71
  72 /* Returns the smallest index k >= 0 for which the bit packet of c consecutive
  73    bits (1 <= c <= 32) is all set in the bitmap consisting of num_words words.
  74    Returns (size_t)(-1) if there is none.  */
  75 static size_t
  76 find_first_packet_set (size_t num_words, const uint32_t *words, size_t c)
  77 {
  78   const uint32_t *ptr = words;
  79   const uint32_t *words_end = words + num_words;
  80   switch (c)
  81     {
  82     case 1:
  83       {
  84         /* A simplified variant of find_first_bit_set.  */
  85         for (; ptr < words_end; ptr++)
  86           {
  87             size_t found = ffs (*ptr);
  88             if (found > 0)
  89               return 32 * (ptr - words) + (found - 1);
  90           }
  91         return (size_t)(-1);
  92       }
  93     case 2:
  94       {
  95         while (ptr < words_end)
  96           {
  97             uint64_t longword = *ptr++;
  98             if (likely (ptr < words_end))
  99               longword |= ((uint64_t) *ptr) << 32;
 100             uint64_t combined = longword & (longword >> 1);
 101             size_t found = ffsll (combined);
 102             if (found > 0)
 103               return 32 * (ptr - 1 - words) + (found - 1);
 104           }
 105         return (size_t)(-1);
 106       }
 107     case 3:
 108       {
 109         while (ptr < words_end)
 110           {
 111             uint64_t longword = *ptr++;
 112             if (likely (ptr < words_end))
 113               longword |= ((uint64_t) *ptr) << 32;
 114             uint64_t combined = longword & (longword >> 1) & (longword >> 2);
 115             size_t found = ffsll (combined);
 116             if (found > 0)
 117               return 32 * (ptr - 1 - words) + (found - 1);
 118           }
 119         return (size_t)(-1);
 120       }
 121     case 4:
 122       {
 123         while (ptr < words_end)
 124           {
 125             uint64_t longword = *ptr++;
 126             if (likely (ptr < words_end))
 127               longword |= ((uint64_t) *ptr) << 32;
 128             uint64_t tmp1 = longword & (longword >> 1);
 129             uint64_t combined = tmp1 & (tmp1 >> 2);
 130             size_t found = ffsll (combined);
 131             if (found > 0)
 132               return 32 * (ptr - 1 - words) + (found - 1);
 133           }
 134         return (size_t)(-1);
 135       }
 136     case 5:
 137       {
 138         while (ptr < words_end)
 139           {
 140             uint64_t longword = *ptr++;
 141             if (likely (ptr < words_end))
 142               longword |= ((uint64_t) *ptr) << 32;
 143             uint64_t tmp1 = longword & (longword >> 1);
 144             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 145             uint64_t combined = tmp2 & (longword >> 4);
 146             size_t found = ffsll (combined);
 147             if (found > 0)
 148               return 32 * (ptr - 1 - words) + (found - 1);
 149           }
 150         return (size_t)(-1);
 151       }
 152     case 6:
 153       {
 154         while (ptr < words_end)
 155           {
 156             uint64_t longword = *ptr++;
 157             if (likely (ptr < words_end))
 158               longword |= ((uint64_t) *ptr) << 32;
 159             uint64_t tmp1 = longword & (longword >> 1);
 160             uint64_t combined = tmp1 & (tmp1 >> 2) & (tmp1 >> 4);
 161             size_t found = ffsll (combined);
 162             if (found > 0)
 163               return 32 * (ptr - 1 - words) + (found - 1);
 164           }
 165         return (size_t)(-1);
 166       }
 167     case 7:
 168       {
 169         while (ptr < words_end)
 170           {
 171             uint64_t longword = *ptr++;
 172             if (likely (ptr < words_end))
 173               longword |= ((uint64_t) *ptr) << 32;
 174             uint64_t tmp1 = longword & (longword >> 1);
 175             uint64_t combined =
 176               tmp1 & (tmp1 >> 2) & (tmp1 >> 4) & (longword >> 6);
 177             size_t found = ffsll (combined);
 178             if (found > 0)
 179               return 32 * (ptr - 1 - words) + (found - 1);
 180           }
 181         return (size_t)(-1);
 182       }
 183     case 8:
 184       {
 185         while (ptr < words_end)
 186           {
 187             uint64_t longword = *ptr++;
 188             if (likely (ptr < words_end))
 189               longword |= ((uint64_t) *ptr) << 32;
 190             uint64_t tmp1 = longword & (longword >> 1);
 191             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 192             uint64_t combined = tmp2 & (tmp2 >> 4);
 193             size_t found = ffsll (combined);
 194             if (found > 0)
 195               return 32 * (ptr - 1 - words) + (found - 1);
 196           }
 197         return (size_t)(-1);
 198       }
 199     case 9:
 200       {
 201         while (ptr < words_end)
 202           {
 203             uint64_t longword = *ptr++;
 204             if (likely (ptr < words_end))
 205               longword |= ((uint64_t) *ptr) << 32;
 206             uint64_t tmp1 = longword & (longword >> 1);
 207             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 208             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 209             uint64_t combined = tmp3 & (longword >> 8);
 210             size_t found = ffsll (combined);
 211             if (found > 0)
 212               return 32 * (ptr - 1 - words) + (found - 1);
 213           }
 214         return (size_t)(-1);
 215       }
 216     case 10:
 217       {
 218         while (ptr < words_end)
 219           {
 220             uint64_t longword = *ptr++;
 221             if (likely (ptr < words_end))
 222               longword |= ((uint64_t) *ptr) << 32;
 223             uint64_t tmp1 = longword & (longword >> 1);
 224             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 225             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 226             uint64_t combined = tmp3 & (tmp1 >> 8);
 227             size_t found = ffsll (combined);
 228             if (found > 0)
 229               return 32 * (ptr - 1 - words) + (found - 1);
 230           }
 231         return (size_t)(-1);
 232       }
 233     case 11:
 234       {
 235         while (ptr < words_end)
 236           {
 237             uint64_t longword = *ptr++;
 238             if (likely (ptr < words_end))
 239               longword |= ((uint64_t) *ptr) << 32;
 240             uint64_t tmp1 = longword & (longword >> 1);
 241             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 242             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 243             uint64_t combined = tmp3 & (tmp1 >> 8) & (longword >> 10);
 244             size_t found = ffsll (combined);
 245             if (found > 0)
 246               return 32 * (ptr - 1 - words) + (found - 1);
 247           }
 248         return (size_t)(-1);
 249       }
 250     case 12:
 251       {
 252         while (ptr < words_end)
 253           {
 254             uint64_t longword = *ptr++;
 255             if (likely (ptr < words_end))
 256               longword |= ((uint64_t) *ptr) << 32;
 257             uint64_t tmp1 = longword & (longword >> 1);
 258             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 259             uint64_t combined = tmp2 & (tmp2 >> 4) & (tmp2 >> 8);
 260             size_t found = ffsll (combined);
 261             if (found > 0)
 262               return 32 * (ptr - 1 - words) + (found - 1);
 263           }
 264         return (size_t)(-1);
 265       }
 266     case 13:
 267       {
 268         while (ptr < words_end)
 269           {
 270             uint64_t longword = *ptr++;
 271             if (likely (ptr < words_end))
 272               longword |= ((uint64_t) *ptr) << 32;
 273             uint64_t tmp1 = longword & (longword >> 1);
 274             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 275             uint64_t combined =
 276               tmp2 & (tmp2 >> 4) & (tmp2 >> 8) & (longword >> 12);
 277             size_t found = ffsll (combined);
 278             if (found > 0)
 279               return 32 * (ptr - 1 - words) + (found - 1);
 280           }
 281         return (size_t)(-1);
 282       }
 283     case 14:
 284       {
 285         while (ptr < words_end)
 286           {
 287             uint64_t longword = *ptr++;
 288             if (likely (ptr < words_end))
 289               longword |= ((uint64_t) *ptr) << 32;
 290             uint64_t tmp1 = longword & (longword >> 1);
 291             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 292             uint64_t combined = tmp2 & (tmp2 >> 4) & (tmp2 >> 8) & (tmp1 >> 12);
 293             size_t found = ffsll (combined);
 294             if (found > 0)
 295               return 32 * (ptr - 1 - words) + (found - 1);
 296           }
 297         return (size_t)(-1);
 298       }
 299     case 15:
 300       {
 301         while (ptr < words_end)
 302           {
 303             uint64_t longword = *ptr++;
 304             if (likely (ptr < words_end))
 305               longword |= ((uint64_t) *ptr) << 32;
 306             /* Optimized: Use 5, not 6, '&' operations.  */
 307             uint64_t tmp1 = longword & (longword >> 1);
 308             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 309             uint64_t tmp3 = tmp2 & (longword >> 4);
 310             uint64_t combined = tmp3 & (tmp3 >> 5) & (tmp3 >> 10);
 311             size_t found = ffsll (combined);
 312             if (found > 0)
 313               return 32 * (ptr - 1 - words) + (found - 1);
 314           }
 315         return (size_t)(-1);
 316       }
 317     case 16:
 318       {
 319         while (ptr < words_end)
 320           {
 321             uint64_t longword = *ptr++;
 322             if (likely (ptr < words_end))
 323               longword |= ((uint64_t) *ptr) << 32;
 324             uint64_t tmp1 = longword & (longword >> 1);
 325             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 326             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 327             uint64_t combined = tmp3 & (tmp3 >> 8);
 328             size_t found = ffsll (combined);
 329             if (found > 0)
 330               return 32 * (ptr - 1 - words) + (found - 1);
 331           }
 332         return (size_t)(-1);
 333       }
 334     case 17:
 335       {
 336         while (ptr < words_end)
 337           {
 338             uint64_t longword = *ptr++;
 339             if (likely (ptr < words_end))
 340               longword |= ((uint64_t) *ptr) << 32;
 341             uint64_t tmp1 = longword & (longword >> 1);
 342             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 343             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 344             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 345             uint64_t combined = tmp4 & (longword >> 16);
 346             size_t found = ffsll (combined);
 347             if (found > 0)
 348               return 32 * (ptr - 1 - words) + (found - 1);
 349           }
 350         return (size_t)(-1);
 351       }
 352     case 18:
 353       {
 354         while (ptr < words_end)
 355           {
 356             uint64_t longword = *ptr++;
 357             if (likely (ptr < words_end))
 358               longword |= ((uint64_t) *ptr) << 32;
 359             uint64_t tmp1 = longword & (longword >> 1);
 360             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 361             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 362             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 363             uint64_t combined = tmp4 & (tmp1 >> 16);
 364             size_t found = ffsll (combined);
 365             if (found > 0)
 366               return 32 * (ptr - 1 - words) + (found - 1);
 367           }
 368         return (size_t)(-1);
 369       }
 370     case 19:
 371       {
 372         while (ptr < words_end)
 373           {
 374             uint64_t longword = *ptr++;
 375             if (likely (ptr < words_end))
 376               longword |= ((uint64_t) *ptr) << 32;
 377             uint64_t tmp1 = longword & (longword >> 1);
 378             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 379             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 380             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 381             uint64_t combined = tmp4 & (tmp1 >> 16) & (longword >> 18);
 382             size_t found = ffsll (combined);
 383             if (found > 0)
 384               return 32 * (ptr - 1 - words) + (found - 1);
 385           }
 386         return (size_t)(-1);
 387       }
 388     case 20:
 389       {
 390         while (ptr < words_end)
 391           {
 392             uint64_t longword = *ptr++;
 393             if (likely (ptr < words_end))
 394               longword |= ((uint64_t) *ptr) << 32;
 395             uint64_t tmp1 = longword & (longword >> 1);
 396             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 397             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 398             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 399             uint64_t combined = tmp4 & (tmp2 >> 16);
 400             size_t found = ffsll (combined);
 401             if (found > 0)
 402               return 32 * (ptr - 1 - words) + (found - 1);
 403           }
 404         return (size_t)(-1);
 405       }
 406     case 21:
 407       {
 408         while (ptr < words_end)
 409           {
 410             uint64_t longword = *ptr++;
 411             if (likely (ptr < words_end))
 412               longword |= ((uint64_t) *ptr) << 32;
 413             uint64_t tmp1 = longword & (longword >> 1);
 414             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 415             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 416             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 417             uint64_t combined = tmp4 & (tmp2 >> 16) & (longword >> 20);
 418             size_t found = ffsll (combined);
 419             if (found > 0)
 420               return 32 * (ptr - 1 - words) + (found - 1);
 421           }
 422         return (size_t)(-1);
 423       }
 424     case 22:
 425       {
 426         while (ptr < words_end)
 427           {
 428             uint64_t longword = *ptr++;
 429             if (likely (ptr < words_end))
 430               longword |= ((uint64_t) *ptr) << 32;
 431             uint64_t tmp1 = longword & (longword >> 1);
 432             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 433             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 434             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 435             uint64_t combined = tmp4 & (tmp2 >> 16) & (tmp1 >> 20);
 436             size_t found = ffsll (combined);
 437             if (found > 0)
 438               return 32 * (ptr - 1 - words) + (found - 1);
 439           }
 440         return (size_t)(-1);
 441       }
 442     case 23:
 443       {
 444         while (ptr < words_end)
 445           {
 446             uint64_t longword = *ptr++;
 447             if (likely (ptr < words_end))
 448               longword |= ((uint64_t) *ptr) << 32;
 449             uint64_t tmp1 = longword & (longword >> 1);
 450             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 451             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 452             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 453             uint64_t combined =
 454               tmp4 & (tmp2 >> 16) & (tmp1 >> 20) & (longword >> 22);
 455             size_t found = ffsll (combined);
 456             if (found > 0)
 457               return 32 * (ptr - 1 - words) + (found - 1);
 458           }
 459         return (size_t)(-1);
 460       }
 461     case 24:
 462       {
 463         while (ptr < words_end)
 464           {
 465             uint64_t longword = *ptr++;
 466             if (likely (ptr < words_end))
 467               longword |= ((uint64_t) *ptr) << 32;
 468             uint64_t tmp1 = longword & (longword >> 1);
 469             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 470             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 471             uint64_t combined = tmp3 & (tmp3 >> 8) & (tmp3 >> 16);
 472             size_t found = ffsll (combined);
 473             if (found > 0)
 474               return 32 * (ptr - 1 - words) + (found - 1);
 475           }
 476         return (size_t)(-1);
 477       }
 478     case 25:
 479       {
 480         while (ptr < words_end)
 481           {
 482             uint64_t longword = *ptr++;
 483             if (likely (ptr < words_end))
 484               longword |= ((uint64_t) *ptr) << 32;
 485             uint64_t tmp1 = longword & (longword >> 1);
 486             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 487             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 488             uint64_t combined =
 489               tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (longword >> 24);
 490             size_t found = ffsll (combined);
 491             if (found > 0)
 492               return 32 * (ptr - 1 - words) + (found - 1);
 493           }
 494         return (size_t)(-1);
 495       }
 496     case 26:
 497       {
 498         while (ptr < words_end)
 499           {
 500             uint64_t longword = *ptr++;
 501             if (likely (ptr < words_end))
 502               longword |= ((uint64_t) *ptr) << 32;
 503             uint64_t tmp1 = longword & (longword >> 1);
 504             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 505             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 506             uint64_t combined =
 507               tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp1 >> 24);
 508             size_t found = ffsll (combined);
 509             if (found > 0)
 510               return 32 * (ptr - 1 - words) + (found - 1);
 511           }
 512         return (size_t)(-1);
 513       }
 514     case 27:
 515       {
 516         while (ptr < words_end)
 517           {
 518             uint64_t longword = *ptr++;
 519             if (likely (ptr < words_end))
 520               longword |= ((uint64_t) *ptr) << 32;
 521             /* Optimized: Use 6, not 7, '&' operations.  */
 522             uint64_t tmp1 = longword & (longword >> 1);
 523             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 524             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 525             uint64_t tmp4 = tmp3 & (longword >> 8);
 526             uint64_t combined = tmp4 & (tmp4 >> 9) & (tmp4 >> 18);
 527             size_t found = ffsll (combined);
 528             if (found > 0)
 529               return 32 * (ptr - 1 - words) + (found - 1);
 530           }
 531         return (size_t)(-1);
 532       }
 533     case 28:
 534       {
 535         while (ptr < words_end)
 536           {
 537             uint64_t longword = *ptr++;
 538             if (likely (ptr < words_end))
 539               longword |= ((uint64_t) *ptr) << 32;
 540             uint64_t tmp1 = longword & (longword >> 1);
 541             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 542             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 543             uint64_t combined =
 544               tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp2 >> 24);
 545             size_t found = ffsll (combined);
 546             if (found > 0)
 547               return 32 * (ptr - 1 - words) + (found - 1);
 548           }
 549         return (size_t)(-1);
 550       }
 551     case 29:
 552       {
 553         while (ptr < words_end)
 554           {
 555             uint64_t longword = *ptr++;
 556             if (likely (ptr < words_end))
 557               longword |= ((uint64_t) *ptr) << 32;
 558             uint64_t tmp1 = longword & (longword >> 1);
 559             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 560             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 561             uint64_t combined =
 562               tmp3 & (tmp3 >> 8) & (tmp3 >> 16) & (tmp2 >> 24) & (longword >> 28);
 563             size_t found = ffsll (combined);
 564             if (found > 0)
 565               return 32 * (ptr - 1 - words) + (found - 1);
 566           }
 567         return (size_t)(-1);
 568       }
 569     case 30:
 570       {
 571         while (ptr < words_end)
 572           {
 573             uint64_t longword = *ptr++;
 574             if (likely (ptr < words_end))
 575               longword |= ((uint64_t) *ptr) << 32;
 576             /* Optimized: Use 6, not 7, '&' operations.  */
 577             uint64_t tmp1 = longword & (longword >> 1);
 578             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 579             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 580             uint64_t tmp4 = tmp3 & (tmp1 >> 8);
 581             uint64_t combined = tmp4 & (tmp4 >> 10) & (tmp4 >> 20);
 582             size_t found = ffsll (combined);
 583             if (found > 0)
 584               return 32 * (ptr - 1 - words) + (found - 1);
 585           }
 586         return (size_t)(-1);
 587       }
 588     case 31:
 589       {
 590         while (ptr < words_end)
 591           {
 592             uint64_t longword = *ptr++;
 593             if (likely (ptr < words_end))
 594               longword |= ((uint64_t) *ptr) << 32;
 595             uint64_t tmp1 = longword & (longword >> 1);
 596             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 597             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 598             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 599             uint64_t combined =
 600               tmp4 & (tmp3 >> 16) & (tmp2 >> 24) & (tmp1 >> 28) & (longword >> 30);
 601             size_t found = ffsll (combined);
 602             if (found > 0)
 603               return 32 * (ptr - 1 - words) + (found - 1);
 604           }
 605         return (size_t)(-1);
 606       }
 607     case 32:
 608       {
 609         while (ptr < words_end)
 610           {
 611             uint64_t longword = *ptr++;
 612             if (likely (ptr < words_end))
 613               longword |= ((uint64_t) *ptr) << 32;
 614             uint64_t tmp1 = longword & (longword >> 1);
 615             uint64_t tmp2 = tmp1 & (tmp1 >> 2);
 616             uint64_t tmp3 = tmp2 & (tmp2 >> 4);
 617             uint64_t tmp4 = tmp3 & (tmp3 >> 8);
 618             uint64_t combined = tmp4 & (tmp4 >> 16);
 619             size_t found = ffsll (combined);
 620             if (found > 0)
 621               return 32 * (ptr - 1 - words) + (found - 1);
 622           }
 623         return (size_t)(-1);
 624       }
 625     default:
 626       /* Invalid argument.  */
 627       abort ();
 628     }
 629 }