This source file includes following definitions.
- init_bitmap_all_bits_clear
- init_bitmap_all_bits_set
- find_first_bit_set
- find_first_packet_set
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
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
45
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
55 {
56 size_t found = ffs (*ptr & (-1U << i0));
57 if (found > 0)
58 return 32 * j0 + (found - 1);
59 }
60
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
73
74
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
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
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
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
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
627 abort ();
628 }
629 }