Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2015 Cisco and/or its affiliates. |
| 3 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | * you may not use this file except in compliance with the License. |
| 5 | * You may obtain a copy of the License at: |
| 6 | * |
| 7 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | * |
| 9 | * Unless required by applicable law or agreed to in writing, software |
| 10 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | * See the License for the specific language governing permissions and |
| 13 | * limitations under the License. |
| 14 | */ |
| 15 | /* |
| 16 | Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus |
| 17 | |
| 18 | Permission is hereby granted, free of charge, to any person obtaining |
| 19 | a copy of this software and associated documentation files (the |
| 20 | "Software"), to deal in the Software without restriction, including |
| 21 | without limitation the rights to use, copy, modify, merge, publish, |
| 22 | distribute, sublicense, and/or sell copies of the Software, and to |
| 23 | permit persons to whom the Software is furnished to do so, subject to |
| 24 | the following conditions: |
| 25 | |
| 26 | The above copyright notice and this permission notice shall be |
| 27 | included in all copies or substantial portions of the Software. |
| 28 | |
| 29 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 30 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 31 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 32 | NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
| 33 | LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
| 34 | OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
| 35 | WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 36 | */ |
| 37 | |
| 38 | #ifndef included_clib_bitmap_h |
| 39 | #define included_clib_bitmap_h |
| 40 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 41 | /** \file |
| 42 | Bitmaps built as vectors of machine words |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 43 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 44 | |
| 45 | #include <vppinfra/vec.h> |
| 46 | #include <vppinfra/random.h> |
| 47 | #include <vppinfra/error.h> |
| 48 | #include <vppinfra/bitops.h> /* for count_set_bits */ |
| 49 | |
Damjan Marion | 0b14072 | 2016-06-14 00:36:09 +0200 | [diff] [blame] | 50 | typedef uword clib_bitmap_t; |
| 51 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 52 | /** predicate function; is an entire bitmap empty? |
| 53 | @param ai - pointer to a bitmap |
| 54 | @returns 1 if the entire bitmap is zero, 0 otherwise |
| 55 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 56 | always_inline uword |
| 57 | clib_bitmap_is_zero (uword * ai) |
| 58 | { |
| 59 | uword i; |
| 60 | for (i = 0; i < vec_len (ai); i++) |
| 61 | if (ai[i] != 0) |
| 62 | return 0; |
| 63 | return 1; |
| 64 | } |
| 65 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 66 | /** predicate function; are two bitmaps equal? |
| 67 | @param a - pointer to a bitmap |
| 68 | @param b - pointer to a bitmap |
| 69 | @returns 1 if the bitmaps are equal, 0 otherwise |
| 70 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 71 | always_inline uword |
| 72 | clib_bitmap_is_equal (uword * a, uword * b) |
| 73 | { |
| 74 | uword i; |
| 75 | if (vec_len (a) != vec_len (b)) |
| 76 | return 0; |
| 77 | for (i = 0; i < vec_len (a); i++) |
| 78 | if (a[i] != b[i]) |
| 79 | return 0; |
| 80 | return 1; |
| 81 | } |
| 82 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 83 | /** Duplicate a bitmap |
Chris Luke | d4024f5 | 2016-09-06 09:32:36 -0400 | [diff] [blame] | 84 | @param v - pointer to a bitmap |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 85 | @returns a duplicate of the bitmap |
| 86 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 87 | #define clib_bitmap_dup(v) vec_dup(v) |
| 88 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 89 | /** Free a bitmap |
| 90 | @param v - pointer to the bitmap to free |
| 91 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 92 | #define clib_bitmap_free(v) vec_free(v) |
| 93 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 94 | /** Number of bytes in a bitmap |
| 95 | @param v - pointer to the bitmap |
| 96 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 97 | #define clib_bitmap_bytes(v) vec_bytes(v) |
| 98 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 99 | /** Clear a bitmap |
| 100 | @param v - pointer to the bitmap to clear |
| 101 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 102 | #define clib_bitmap_zero(v) vec_zero(v) |
| 103 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 104 | /** Allocate a bitmap with the supplied number of bits |
| 105 | @param [out] v - the resulting bitmap |
| 106 | @param n_bits - the required number of bits |
| 107 | */ |
| 108 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 109 | #define clib_bitmap_alloc(v,n_bits) \ |
| 110 | v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword)) |
| 111 | |
| 112 | #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword)) |
| 113 | |
| 114 | /* Make sure that a bitmap is at least n_bits in size */ |
| 115 | #define clib_bitmap_validate(v,n_bits) \ |
| 116 | clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword)) |
| 117 | |
| 118 | /* low-level routine to remove trailing zeros from a bitmap */ |
| 119 | always_inline uword * |
| 120 | _clib_bitmap_remove_trailing_zeros (uword * a) |
| 121 | { |
| 122 | word i; |
| 123 | if (a) |
| 124 | { |
| 125 | for (i = _vec_len (a) - 1; i >= 0; i--) |
| 126 | if (a[i] != 0) |
| 127 | break; |
| 128 | _vec_len (a) = i + 1; |
| 129 | } |
| 130 | return a; |
| 131 | } |
| 132 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 133 | /** Sets the ith bit of a bitmap to new_value. |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 134 | No sanity checking. Be careful. |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 135 | @param a - pointer to the bitmap |
| 136 | @param i - the bit position to interrogate |
| 137 | @param new_value - new value for the bit |
| 138 | @returns the old value of the bit |
| 139 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 140 | always_inline uword |
| 141 | clib_bitmap_set_no_check (uword * a, uword i, uword new_value) |
| 142 | { |
| 143 | uword i0 = i / BITS (a[0]); |
| 144 | uword i1 = i % BITS (a[0]); |
| 145 | uword bit = (uword) 1 << i1; |
| 146 | uword ai, old_value; |
| 147 | |
| 148 | /* Removed ASSERT since uword * a may not be a vector. */ |
| 149 | /* ASSERT (i0 < vec_len (a)); */ |
| 150 | |
| 151 | ai = a[i0]; |
| 152 | old_value = (ai & bit) != 0; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 153 | ai &= ~bit; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 154 | ai |= ((uword) (new_value != 0)) << i1; |
| 155 | a[i0] = ai; |
| 156 | return old_value; |
| 157 | } |
| 158 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 159 | /** Sets the ith bit of a bitmap to new_value |
| 160 | Removes trailing zeros from the bitmap |
Chris Luke | d4024f5 | 2016-09-06 09:32:36 -0400 | [diff] [blame] | 161 | @param ai - pointer to the bitmap |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 162 | @param i - the bit position to interrogate |
Chris Luke | d4024f5 | 2016-09-06 09:32:36 -0400 | [diff] [blame] | 163 | @param value - new value for the bit |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 164 | @returns the old value of the bit |
| 165 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 166 | always_inline uword * |
| 167 | clib_bitmap_set (uword * ai, uword i, uword value) |
| 168 | { |
| 169 | uword i0 = i / BITS (ai[0]); |
| 170 | uword i1 = i % BITS (ai[0]); |
| 171 | uword a; |
| 172 | |
| 173 | /* Check for writing a zero to beyond end of bitmap. */ |
| 174 | if (value == 0 && i0 >= vec_len (ai)) |
| 175 | return ai; /* Implied trailing zeros. */ |
| 176 | |
| 177 | clib_bitmap_vec_validate (ai, i0); |
| 178 | |
| 179 | a = ai[i0]; |
| 180 | a &= ~((uword) 1 << i1); |
| 181 | a |= ((uword) (value != 0)) << i1; |
| 182 | ai[i0] = a; |
| 183 | |
| 184 | /* If bits have been cleared, test for zero. */ |
| 185 | if (a == 0) |
| 186 | ai = _clib_bitmap_remove_trailing_zeros (ai); |
| 187 | |
| 188 | return ai; |
| 189 | } |
| 190 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 191 | /** Gets the ith bit value from a bitmap |
| 192 | @param ai - pointer to the bitmap |
| 193 | @param i - the bit position to interrogate |
| 194 | @returns the indicated bit value |
| 195 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 196 | always_inline uword |
| 197 | clib_bitmap_get (uword * ai, uword i) |
| 198 | { |
| 199 | uword i0 = i / BITS (ai[0]); |
| 200 | uword i1 = i % BITS (ai[0]); |
| 201 | return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1); |
| 202 | } |
| 203 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 204 | /** Gets the ith bit value from a bitmap |
| 205 | Does not sanity-check the bit position. Be careful. |
| 206 | @param ai - pointer to the bitmap |
| 207 | @param i - the bit position to interrogate |
| 208 | @returns the indicated bit value, or garbage if the bit position is |
| 209 | out of range. |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 210 | */ |
| 211 | always_inline uword |
| 212 | clib_bitmap_get_no_check (uword * ai, uword i) |
| 213 | { |
| 214 | uword i0 = i / BITS (ai[0]); |
| 215 | uword i1 = i % BITS (ai[0]); |
| 216 | return 0 != ((ai[i0] >> i1) & 1); |
| 217 | } |
| 218 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 219 | always_inline uword |
| 220 | clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits) |
| 221 | { |
| 222 | uword i0 = i / BITS (ai[0]); |
| 223 | uword i1 = i % BITS (ai[0]); |
| 224 | ASSERT (i1 + n_bits <= BITS (uword)); |
| 225 | return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits)); |
| 226 | } |
| 227 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 228 | /** Gets the ith through ith + n_bits bit values from a bitmap |
| 229 | @param bitmap - pointer to the bitmap |
| 230 | @param i - the first bit position to retrieve |
| 231 | @param n_bits - the number of bit positions to retrieve |
| 232 | @returns the indicated range of bits |
| 233 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 234 | always_inline uword |
| 235 | clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits) |
| 236 | { |
| 237 | uword i0, i1, result; |
| 238 | uword l = vec_len (bitmap); |
| 239 | |
Dave Barach | f9c231e | 2016-08-05 10:10:18 -0400 | [diff] [blame] | 240 | ASSERT (n_bits <= BITS (result)); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 241 | |
| 242 | i0 = i / BITS (bitmap[0]); |
| 243 | i1 = i % BITS (bitmap[0]); |
| 244 | |
| 245 | /* Check first word. */ |
| 246 | result = 0; |
| 247 | if (i0 < l) |
| 248 | { |
| 249 | result |= (bitmap[i0] >> i1); |
| 250 | if (n_bits < BITS (bitmap[0])) |
| 251 | result &= (((uword) 1 << n_bits) - 1); |
| 252 | } |
| 253 | |
| 254 | /* Check for overlap into next word. */ |
| 255 | i0++; |
| 256 | if (i1 + n_bits > BITS (bitmap[0]) && i0 < l) |
| 257 | { |
| 258 | n_bits -= BITS (bitmap[0]) - i1; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 259 | result |= |
| 260 | (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 261 | } |
| 262 | |
| 263 | return result; |
| 264 | } |
| 265 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 266 | /** sets the ith through ith + n_bits bits in a bitmap |
| 267 | @param bitmap - pointer to the bitmap |
| 268 | @param i - the first bit position to retrieve |
| 269 | @param value - the values to set |
| 270 | @param n_bits - the number of bit positions to set |
| 271 | @returns a pointer to the updated bitmap, which may expand and move |
| 272 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 273 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 274 | always_inline uword * |
| 275 | clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits) |
| 276 | { |
| 277 | uword i0, i1, l, t, m; |
| 278 | |
Dave Barach | f9c231e | 2016-08-05 10:10:18 -0400 | [diff] [blame] | 279 | ASSERT (n_bits <= BITS (value)); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 280 | |
| 281 | i0 = i / BITS (bitmap[0]); |
| 282 | i1 = i % BITS (bitmap[0]); |
| 283 | |
| 284 | /* Allocate bitmap. */ |
| 285 | clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0])); |
| 286 | l = vec_len (bitmap); |
| 287 | |
| 288 | m = ~0; |
| 289 | if (n_bits < BITS (value)) |
| 290 | m = (((uword) 1 << n_bits) - 1); |
| 291 | value &= m; |
| 292 | |
| 293 | /* Insert into first word. */ |
| 294 | t = bitmap[i0]; |
| 295 | t &= ~(m << i1); |
| 296 | t |= value << i1; |
| 297 | bitmap[i0] = t; |
| 298 | |
| 299 | /* Insert into second word. */ |
| 300 | i0++; |
| 301 | if (i1 + n_bits > BITS (bitmap[0]) && i0 < l) |
| 302 | { |
| 303 | t = BITS (bitmap[0]) - i1; |
| 304 | value >>= t; |
| 305 | n_bits -= t; |
| 306 | t = bitmap[i0]; |
| 307 | m = ((uword) 1 << n_bits) - 1; |
| 308 | t &= ~m; |
| 309 | t |= value; |
| 310 | bitmap[i0] = t; |
| 311 | } |
| 312 | |
| 313 | return bitmap; |
| 314 | } |
| 315 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 316 | always_inline uword * |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 317 | clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 318 | { |
| 319 | uword a0, a1, b0; |
| 320 | uword i_end, mask; |
| 321 | |
| 322 | a0 = i / BITS (bitmap[0]); |
| 323 | a1 = i % BITS (bitmap[0]); |
| 324 | |
| 325 | i_end = i + n_bits; |
| 326 | b0 = i_end / BITS (bitmap[0]); |
| 327 | |
| 328 | clib_bitmap_vec_validate (bitmap, b0); |
| 329 | |
| 330 | /* First word. */ |
| 331 | mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0; |
| 332 | mask <<= a1; |
| 333 | |
| 334 | if (value) |
| 335 | bitmap[a0] |= mask; |
| 336 | else |
| 337 | bitmap[a0] &= ~mask; |
| 338 | |
| 339 | for (a0++; a0 < b0; a0++) |
| 340 | bitmap[a0] = value ? ~0 : 0; |
| 341 | |
| 342 | if (a0 == b0) |
| 343 | { |
| 344 | word n_bits_left = n_bits - (BITS (bitmap[0]) - a1); |
| 345 | mask = pow2_mask (n_bits_left); |
| 346 | if (value) |
| 347 | bitmap[a0] |= mask; |
| 348 | else |
| 349 | bitmap[a0] &= ~mask; |
| 350 | } |
| 351 | |
| 352 | return bitmap; |
| 353 | } |
| 354 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 355 | /** Macro to iterate across set bits in a bitmap |
| 356 | |
| 357 | @param i - the current set bit |
| 358 | @param ai - the bitmap |
| 359 | @param body - the expression to evaluate for each set bit |
| 360 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 361 | #define clib_bitmap_foreach(i,ai,body) \ |
| 362 | do { \ |
| 363 | uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \ |
| 364 | __bitmap_len = vec_len ((ai)); \ |
| 365 | for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \ |
| 366 | { \ |
| 367 | __bitmap_ai = (ai)[__bitmap_i]; \ |
| 368 | while (__bitmap_ai != 0) \ |
| 369 | { \ |
| 370 | __bitmap_first_set = first_set (__bitmap_ai); \ |
| 371 | (i) = (__bitmap_i * BITS ((ai)[0]) \ |
| 372 | + min_log2 (__bitmap_first_set)); \ |
| 373 | do { body; } while (0); \ |
| 374 | __bitmap_ai ^= __bitmap_first_set; \ |
| 375 | } \ |
| 376 | } \ |
| 377 | } while (0) |
| 378 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 379 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 380 | /** Return the lowest numbered set bit in a bitmap |
| 381 | @param ai - pointer to the bitmap |
| 382 | @returns lowest numbered set bit, or ~0 if the entire bitmap is zero |
| 383 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 384 | always_inline uword |
| 385 | clib_bitmap_first_set (uword * ai) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 386 | { |
| 387 | uword i; |
| 388 | for (i = 0; i < vec_len (ai); i++) |
| 389 | { |
| 390 | uword x = ai[i]; |
| 391 | if (x != 0) |
| 392 | return i * BITS (ai[0]) + log2_first_set (x); |
| 393 | } |
| 394 | return ~0; |
| 395 | } |
| 396 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 397 | /** Return the higest numbered set bit in a bitmap |
| 398 | @param ai - pointer to the bitmap |
| 399 | @returns lowest numbered set bit, or ~0 if the entire bitmap is zero |
| 400 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 401 | always_inline uword |
| 402 | clib_bitmap_last_set (uword * ai) |
Damjan Marion | 0247b46 | 2016-06-08 01:37:11 +0200 | [diff] [blame] | 403 | { |
| 404 | uword i; |
| 405 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 406 | for (i = vec_len (ai); i > 0; i--) |
Damjan Marion | 0247b46 | 2016-06-08 01:37:11 +0200 | [diff] [blame] | 407 | { |
Damjan Marion | ec17510 | 2016-06-30 01:02:17 +0200 | [diff] [blame] | 408 | uword x = ai[i - 1]; |
Damjan Marion | 0247b46 | 2016-06-08 01:37:11 +0200 | [diff] [blame] | 409 | if (x != 0) |
| 410 | { |
| 411 | uword first_bit; |
Damjan Marion | 1105600 | 2018-05-10 13:40:44 +0200 | [diff] [blame^] | 412 | first_bit = count_leading_zeros (x); |
Damjan Marion | ec17510 | 2016-06-30 01:02:17 +0200 | [diff] [blame] | 413 | return (i) * BITS (ai[0]) - first_bit - 1; |
Damjan Marion | 0247b46 | 2016-06-08 01:37:11 +0200 | [diff] [blame] | 414 | } |
| 415 | } |
| 416 | return ~0; |
| 417 | } |
| 418 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 419 | /** Return the lowest numbered clear bit in a bitmap |
| 420 | @param ai - pointer to the bitmap |
| 421 | @returns lowest numbered clear bit |
| 422 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 423 | always_inline uword |
| 424 | clib_bitmap_first_clear (uword * ai) |
| 425 | { |
| 426 | uword i; |
| 427 | for (i = 0; i < vec_len (ai); i++) |
| 428 | { |
| 429 | uword x = ~ai[i]; |
| 430 | if (x != 0) |
| 431 | return i * BITS (ai[0]) + log2_first_set (x); |
| 432 | } |
| 433 | return i * BITS (ai[0]); |
| 434 | } |
| 435 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 436 | /** Return the number of set bits in a bitmap |
| 437 | @param ai - pointer to the bitmap |
| 438 | @returns the number of set bits in the bitmap |
| 439 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 440 | always_inline uword |
| 441 | clib_bitmap_count_set_bits (uword * ai) |
| 442 | { |
| 443 | uword i; |
| 444 | uword n_set = 0; |
| 445 | for (i = 0; i < vec_len (ai); i++) |
| 446 | n_set += count_set_bits (ai[i]); |
| 447 | return n_set; |
| 448 | } |
| 449 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 450 | /** Logical operator across two bitmaps |
| 451 | |
| 452 | @param ai - pointer to the destination bitmap |
| 453 | @param bi - pointer to the source bitmap |
| 454 | @returns ai = ai and bi. ai is modified, bi is not modified |
| 455 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 456 | always_inline uword *clib_bitmap_and (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 457 | |
| 458 | /** Logical operator across two bitmaps |
| 459 | |
| 460 | @param ai - pointer to the destination bitmap |
| 461 | @param bi - pointer to the source bitmap |
| 462 | @returns ai = ai & ~bi. ai is modified, bi is not modified |
| 463 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 464 | always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 465 | |
| 466 | /** Logical operator across two bitmaps |
| 467 | |
| 468 | @param ai - pointer to the destination bitmap |
| 469 | @param bi - pointer to the source bitmap |
| 470 | @returns ai = ai & ~bi. ai is modified, bi is not modified |
| 471 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 472 | always_inline uword *clib_bitmap_or (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 473 | /** Logical operator across two bitmaps |
| 474 | |
| 475 | @param ai - pointer to the destination bitmap |
| 476 | @param bi - pointer to the source bitmap |
| 477 | @returns ai = ai or bi. ai is modified, bi is not modified |
| 478 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 479 | always_inline uword *clib_bitmap_or (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 480 | |
| 481 | /** Logical operator across two bitmaps |
| 482 | |
| 483 | @param ai - pointer to the destination bitmap |
| 484 | @param bi - pointer to the source bitmap |
| 485 | @returns ai = ai xor bi. ai is modified, bi is not modified |
| 486 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 487 | always_inline uword *clib_bitmap_xor (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 488 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 489 | /* ALU function definition macro for functions taking two bitmaps. */ |
| 490 | #define _(name, body, check_zero) \ |
| 491 | always_inline uword * \ |
| 492 | clib_bitmap_##name (uword * ai, uword * bi) \ |
| 493 | { \ |
| 494 | uword i, a, b, bi_len, n_trailing_zeros; \ |
| 495 | \ |
| 496 | n_trailing_zeros = 0; \ |
| 497 | bi_len = vec_len (bi); \ |
| 498 | if (bi_len > 0) \ |
| 499 | clib_bitmap_vec_validate (ai, bi_len - 1); \ |
| 500 | for (i = 0; i < vec_len (ai); i++) \ |
| 501 | { \ |
| 502 | a = ai[i]; \ |
| 503 | b = i < bi_len ? bi[i] : 0; \ |
| 504 | do { body; } while (0); \ |
| 505 | ai[i] = a; \ |
| 506 | if (check_zero) \ |
| 507 | n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \ |
| 508 | } \ |
| 509 | if (check_zero) \ |
| 510 | _vec_len (ai) -= n_trailing_zeros; \ |
| 511 | return ai; \ |
| 512 | } |
| 513 | |
| 514 | /* ALU functions: */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 515 | _(and, a = a & b, 1) |
| 516 | _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 517 | #undef _ |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 518 | /** Logical operator across two bitmaps which duplicates the first bitmap |
| 519 | |
| 520 | @param ai - pointer to the destination bitmap |
| 521 | @param bi - pointer to the source bitmap |
| 522 | @returns aiDup = ai and bi. Neither ai nor bi are modified |
| 523 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 524 | always_inline uword * |
| 525 | clib_bitmap_dup_and (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 526 | |
| 527 | /** Logical operator across two bitmaps which duplicates the first bitmap |
| 528 | |
| 529 | @param ai - pointer to the destination bitmap |
| 530 | @param bi - pointer to the source bitmap |
| 531 | @returns aiDup = ai & ~bi. Neither ai nor bi are modified |
| 532 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 533 | always_inline uword * |
| 534 | clib_bitmap_dup_andnot (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 535 | |
| 536 | /** Logical operator across two bitmaps which duplicates the first bitmap |
| 537 | |
| 538 | @param ai - pointer to the destination bitmap |
| 539 | @param bi - pointer to the source bitmap |
| 540 | @returns aiDup = ai or bi. Neither ai nor bi are modified |
| 541 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 542 | always_inline uword * |
| 543 | clib_bitmap_dup_or (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 544 | |
| 545 | /** Logical operator across two bitmaps which duplicates the first bitmap |
| 546 | |
| 547 | @param ai - pointer to the destination bitmap |
| 548 | @param bi - pointer to the source bitmap |
| 549 | @returns aiDup = ai xor bi. Neither ai nor bi are modified |
| 550 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 551 | always_inline uword * |
| 552 | clib_bitmap_dup_xor (uword * ai, uword * bi); |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 553 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 554 | #define _(name) \ |
| 555 | always_inline uword * \ |
| 556 | clib_bitmap_dup_##name (uword * ai, uword * bi) \ |
| 557 | { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); } |
| 558 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 559 | _(and); |
| 560 | _(andnot); |
| 561 | _(or); |
| 562 | _(xor); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 563 | |
| 564 | #undef _ |
| 565 | |
| 566 | /* ALU function definition macro for functions taking one bitmap and an immediate. */ |
| 567 | #define _(name, body, check_zero) \ |
| 568 | always_inline uword * \ |
| 569 | clib_bitmap_##name (uword * ai, uword i) \ |
| 570 | { \ |
| 571 | uword i0 = i / BITS (ai[0]); \ |
| 572 | uword i1 = i % BITS (ai[0]); \ |
| 573 | uword a, b; \ |
| 574 | clib_bitmap_vec_validate (ai, i0); \ |
| 575 | a = ai[i0]; \ |
| 576 | b = (uword) 1 << i1; \ |
| 577 | do { body; } while (0); \ |
| 578 | ai[i0] = a; \ |
| 579 | if (check_zero && a == 0) \ |
| 580 | ai = _clib_bitmap_remove_trailing_zeros (ai); \ |
| 581 | return ai; \ |
| 582 | } |
| 583 | |
| 584 | /* ALU functions immediate: */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 585 | _(andi, a = a & b, 1) |
| 586 | _(andnoti, a = a & ~b, 1) _(ori, a = a | b, 0) _(xori, a = a ^ b, 1) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 587 | #undef _ |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 588 | /** Return a random bitmap of the requested length |
| 589 | @param ai - pointer to the destination bitmap |
| 590 | @param n_bits - number of bits to allocate |
Chris Luke | d4024f5 | 2016-09-06 09:32:36 -0400 | [diff] [blame] | 591 | @param [in,out] seed - pointer to the random number seed |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 592 | @returns a reasonably random bitmap based. See random.h. |
| 593 | */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 594 | always_inline uword * |
| 595 | clib_bitmap_random (uword * ai, uword n_bits, u32 * seed) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 596 | { |
| 597 | vec_reset_length (ai); |
| 598 | |
| 599 | if (n_bits > 0) |
| 600 | { |
| 601 | uword i = n_bits - 1; |
| 602 | uword i0, i1; |
| 603 | uword log2_rand_max; |
| 604 | |
| 605 | log2_rand_max = min_log2 (random_u32_max ()); |
| 606 | |
| 607 | i0 = i / BITS (ai[0]); |
| 608 | i1 = i % BITS (ai[0]); |
| 609 | |
| 610 | clib_bitmap_vec_validate (ai, i0); |
| 611 | for (i = 0; i <= i0; i++) |
| 612 | { |
| 613 | uword n; |
| 614 | for (n = 0; n < BITS (ai[i]); n += log2_rand_max) |
| 615 | ai[i] |= random_u32 (seed) << n; |
| 616 | } |
| 617 | if (i1 + 1 < BITS (ai[0])) |
| 618 | ai[i0] &= (((uword) 1 << (i1 + 1)) - 1); |
| 619 | } |
| 620 | return ai; |
| 621 | } |
| 622 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 623 | /** Return the next set bit in a bitmap starting at bit i |
| 624 | @param ai - pointer to the bitmap |
| 625 | @param i - first bit position to test |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 626 | @returns first set bit position at or after i, |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 627 | ~0 if no further set bits are found |
| 628 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 629 | always_inline uword |
| 630 | clib_bitmap_next_set (uword * ai, uword i) |
| 631 | { |
| 632 | uword i0 = i / BITS (ai[0]); |
| 633 | uword i1 = i % BITS (ai[0]); |
| 634 | uword t; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 635 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 636 | if (i0 < vec_len (ai)) |
| 637 | { |
| 638 | t = (ai[i0] >> i1) << i1; |
| 639 | if (t) |
| 640 | return log2_first_set (t) + i0 * BITS (ai[0]); |
| 641 | |
| 642 | for (i0++; i0 < vec_len (ai); i0++) |
| 643 | { |
| 644 | t = ai[i0]; |
| 645 | if (t) |
| 646 | return log2_first_set (t) + i0 * BITS (ai[0]); |
| 647 | } |
| 648 | } |
| 649 | |
| 650 | return ~0; |
| 651 | } |
| 652 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 653 | /** Return the next clear bit in a bitmap starting at bit i |
| 654 | @param ai - pointer to the bitmap |
| 655 | @param i - first bit position to test |
| 656 | @returns first clear bit position at or after i |
| 657 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 658 | always_inline uword |
| 659 | clib_bitmap_next_clear (uword * ai, uword i) |
| 660 | { |
| 661 | uword i0 = i / BITS (ai[0]); |
| 662 | uword i1 = i % BITS (ai[0]); |
| 663 | uword t; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 664 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 665 | if (i0 < vec_len (ai)) |
| 666 | { |
| 667 | t = (~ai[i0] >> i1) << i1; |
| 668 | if (t) |
| 669 | return log2_first_set (t) + i0 * BITS (ai[0]); |
| 670 | |
| 671 | for (i0++; i0 < vec_len (ai); i0++) |
| 672 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 673 | t = ~ai[i0]; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 674 | if (t) |
| 675 | return log2_first_set (t) + i0 * BITS (ai[0]); |
| 676 | } |
| 677 | } |
| 678 | return i; |
| 679 | } |
| 680 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 681 | /** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" ) |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 682 | |
| 683 | uword * bitmap; |
| 684 | rv = unformat ("%U", unformat_bitmap_list, &bitmap); |
| 685 | |
| 686 | Standard unformat_function_t arguments |
| 687 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 688 | @param input - pointer an unformat_input_t |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 689 | @param va - varargs list comprising a single uword ** |
| 690 | @returns 1 on success, 0 on failure |
| 691 | */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 692 | static inline uword |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 693 | unformat_bitmap_list (unformat_input_t * input, va_list * va) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 694 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 695 | uword **bitmap_return = va_arg (*va, uword **); |
| 696 | uword *bitmap = 0; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 697 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 698 | u32 a, b; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 699 | |
| 700 | while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) |
| 701 | { |
| 702 | int i; |
| 703 | if (unformat (input, "%u-%u,", &a, &b)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 704 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 705 | else if (unformat (input, "%u,", &a)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 706 | b = a; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 707 | else if (unformat (input, "%u-%u", &a, &b)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 708 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 709 | else if (unformat (input, "%u", &a)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 710 | b = a; |
Damjan Marion | 75d1f24 | 2016-01-19 14:06:32 +0100 | [diff] [blame] | 711 | else if (bitmap) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 712 | { |
| 713 | unformat_put_input (input); |
Damjan Marion | 75d1f24 | 2016-01-19 14:06:32 +0100 | [diff] [blame] | 714 | break; |
| 715 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 716 | else |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 717 | goto error; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 718 | |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 719 | if (b < a) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 720 | goto error; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 721 | |
| 722 | for (i = a; i <= b; i++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 723 | bitmap = clib_bitmap_set (bitmap, i, 1); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 724 | } |
| 725 | *bitmap_return = bitmap; |
| 726 | return 1; |
| 727 | error: |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 728 | clib_bitmap_free (bitmap); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 729 | return 0; |
| 730 | } |
| 731 | |
Dave Barach | 310f7fe | 2016-08-05 14:36:27 -0400 | [diff] [blame] | 732 | /** Format a bitmap as a string of hex bytes |
| 733 | |
| 734 | uword * bitmap; |
| 735 | s = format ("%U", format_bitmap_hex, bitmap); |
| 736 | |
| 737 | Standard format_function_t arguments |
| 738 | |
| 739 | @param s - string under construction |
| 740 | @param args - varargs list comprising a single uword * |
| 741 | @returns string under construction |
| 742 | */ |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 743 | static inline u8 * |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 744 | format_bitmap_hex (u8 * s, va_list * args) |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 745 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 746 | uword *bitmap = va_arg (*args, uword *); |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 747 | int i, is_trailing_zero = 1; |
| 748 | |
| 749 | if (!bitmap) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 750 | return format (s, "0"); |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 751 | |
| 752 | i = vec_bytes (bitmap) * 2; |
| 753 | |
| 754 | while (i > 0) |
| 755 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 756 | u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4); |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 757 | |
| 758 | if (x && is_trailing_zero) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 759 | is_trailing_zero = 0; |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 760 | |
| 761 | if (x || !is_trailing_zero) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 762 | s = format (s, "%x", x); |
Damjan Marion | 14a44d3 | 2016-02-05 23:33:21 +0100 | [diff] [blame] | 763 | } |
| 764 | return s; |
| 765 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 766 | #endif /* included_clib_bitmap_h */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 767 | |
| 768 | /* |
| 769 | * fd.io coding-style-patch-verification: ON |
| 770 | * |
| 771 | * Local Variables: |
| 772 | * eval: (c-set-style "gnu") |
| 773 | * End: |
| 774 | */ |