summaryrefslogtreecommitdiffstats
path: root/acl
AgeCommit message (Collapse)AuthorFilesLines
2017-01-18HONEYCOMB-330: fix acl tag handlingMarek Gradzki14-45/+59
Acl tag in vpp's acl plugin is an ascii tag, so it should not be handled as hex string. Change-Id: I801d5b72a4c20f78246288ea63d914b0b9f3564b Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2017-01-16HC2VPP-38 / HONEYCOMB-336 - removed mandatory from ace-ip-versionJan Srnicek8-49/+656
Removed mandatory statements Fixed multiple NPE Change-Id: I30af417b0594d9634a9352f7721285257fbcee1e Signed-off-by: Jan Srnicek <jsrnicek@cisco.com>
2017-01-11Bump of jvpp version to 17.04Jan Srnicek1-1/+1
Depends on https://gerrit.fd.io/r/#/c/4632/ Nsh stays on 17.01, till owner provides higher version Change-Id: I1f51699b6809d30dd0272301ebb1074a42863618 Signed-off-by: Jan Srnicek <jsrnicek@cisco.com>
2017-01-11Fix NPE in L3 rulesMarek Gradzki5-17/+130
Patch introduces proper handling for IP adresses, which are optional. Change-Id: Ib009207b4b241d3e2b8c665a35bb1ff87b4a12ac Signed-off-by: Marek Gradzki <mgradzki@cisco.com> (cherry picked from commit e0b4359b39acfe8a583089117a0c2485b85ff7e4)
2017-01-10Fixing NPE in TCP/UDP L4 rulesMarek Gradzki3-17/+106
Change-Id: Iae90f081c0add7ad9f6dd22229df683c6d395e78 Signed-off-by: Tomas Cechvala <tcechval@cisco.com> Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2017-01-10HC2VPP-31: fix vpp-ace translation with no protocol setMarek Gradzki4-2/+46
Change-Id: I9d319ae3d04d90c7652828b0cb382ad142f9d2b6 Signed-off-by: Marek Gradzki <mgradzki@cisco.com> (cherry picked from commit 1b7a019ae9ceeddee496b20f83c095ffcb87b6c2)
2017-01-05Bump hc2vpp versoin to 17.04Marek Gradzki3-6/+6
Also updates version of honeycomb dependencies. Vpp API version bump moved to separate commit due to issues with jvpp jars. Change-Id: Id336393b00fe05e8ecee9b547dcfc6a49e1a98ec Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2017-01-04HONEYCOMB-310: readers&initializers for vpp and macip aclsMarek Gradzki30-155/+1122
Change-Id: I8892479123091e43bf191c544b6628d6254be564 Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-23HONEYCOMB-310: initializers for interface acl assignmentMarek Gradzki7-13/+109
Change-Id: I6dcc1ef1abc9d314906d6d4fcc746dcfd28ec5fc Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-22Fix non existing tag handling for mac-ip customizerMarek Gradzki3-21/+134
Change-Id: I717ea660a773cfd3b56010dbfe1e5691bde32de8 Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-22Fix ingress/egress acl assignment readMarek Gradzki9-230/+364
Ingress and egress acls are not anymore mixed on the same list when reading interface state Change-Id: I2f775db4482e61593aa9689afcb687f7db7b4e73 Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-21Fix interface read when alcs are not configuredMarek Gradzki4-2/+218
Change-Id: Id780d9f503901d551f5a9d5693ca0a28cf596a5c Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-20HONEYCOMB-310: postman collection for acl pluginMarek Gradzki1-0/+223
Change-Id: I4eb0c7df35577488259e48da7b32ae0a6c47de56 Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-20HONEYCOMB-310: translation layer for acl pluginJan Srnicek41-0/+3563
Not covered by this patch (moved to subsequent commits): - postman collection - distinguish ingress/egress ACLs while reading assigned acls - proper support for acl tag - unit tests improvements - read for acls (not necessarily assigned) - initializers Change-Id: I5a198ce1a6e20d0b1d95b4d2d83d0464fb86580c Signed-off-by: Jan Srnicek <jsrnicek@cisco.com> Signed-off-by: Marek Gradzki <mgradzki@cisco.com>
2016-12-16HONEYCOMB-321 - Acl model fix to not break yang specificationJan Srnicek1-27/+41
Prevents breaking 7.9.2. The choice's case Statement from Yang RFC Change-Id: I1895afbdd6c2209262575925463dcfde7d2c649d Signed-off-by: Jan Srnicek <jsrnicek@cisco.com>
2016-12-14Acl model improvementsJan Srnicek1-5/+16
Adds case to cover other protocol numbers Adds constraint to not allow stateless mac-ip acl's Change-Id: I9feeba5ac6b6480282cac62e5479c433c92c8d99 Signed-off-by: Jan Srnicek <jsrnicek@cisco.com>
2016-12-09Allow setting icmp code range for alc'sJan Srnicek1-16/+25
Change-Id: I712f25f70f1a6186b9fe888f7a560616cfd9aeb6 Signed-off-by: Jan Srnicek <jsrnicek@cisco.com>
2016-12-08HONEYCOMB-304: yang model for the acl pluginMarek Gradzki6-0/+423
Change-Id: Ic5d11961d5e620d171cd6e320879fd3de507b055 Signed-off-by: Marek Gradzki <mgradzki@cisco.com> Signed-off-by: Jan Srnicek <jsrnicek@cisco.com>
3' href='#n493'>493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 
/*
 * Copyright (c) 2015 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
  Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus

  Permission is hereby granted, free of charge, to any person obtaining
  a copy of this software and associated documentation files (the
  "Software"), to deal in the Software without restriction, including
  without limitation the rights to use, copy, modify, merge, publish,
  distribute, sublicense, and/or sell copies of the Software, and to
  permit persons to whom the Software is furnished to do so, subject to
  the following conditions:

  The above copyright notice and this permission notice shall be
  included in all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#ifndef included_clib_bitmap_h
#define included_clib_bitmap_h

/** \file
    Bitmaps built as vectors of machine words
*/

#include <vppinfra/vec.h>
#include <vppinfra/random.h>
#include <vppinfra/error.h>
#include <vppinfra/bitops.h>	/* for count_set_bits */

typedef uword clib_bitmap_t;

/** predicate function; is an entire bitmap empty?
    @param ai - pointer to a bitmap
    @returns 1 if the entire bitmap is zero, 0 otherwise
*/
always_inline uword
clib_bitmap_is_zero (uword * ai)
{
  uword i;
  for (i = 0; i < vec_len (ai); i++)
    if (ai[i] != 0)
      return 0;
  return 1;
}

/** predicate function; are two bitmaps equal?
    @param a - pointer to a bitmap
    @param b - pointer to a bitmap
    @returns 1 if the bitmaps are equal, 0 otherwise
*/
always_inline uword
clib_bitmap_is_equal (uword * a, uword * b)
{
  uword i;
  if (vec_len (a) != vec_len (b))
    return 0;
  for (i = 0; i < vec_len (a); i++)
    if (a[i] != b[i])
      return 0;
  return 1;
}

/** Duplicate a bitmap
    @param v - pointer to a bitmap
    @returns a duplicate of the bitmap
*/
#define clib_bitmap_dup(v) vec_dup(v)

/** Free a bitmap
    @param v - pointer to the bitmap to free
*/
#define clib_bitmap_free(v) vec_free(v)

/** Number of bytes in a bitmap
    @param v - pointer to the bitmap
*/
#define clib_bitmap_bytes(v) vec_bytes(v)

/** Clear a bitmap
    @param v - pointer to the bitmap to clear
*/
#define clib_bitmap_zero(v) vec_zero(v)

/** Allocate a bitmap with the supplied number of bits
    @param [out] v - the resulting bitmap
    @param n_bits - the required number of bits
*/

#define clib_bitmap_alloc(v,n_bits) \
  v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))

#define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))

/* Make sure that a bitmap is at least n_bits in size */
#define clib_bitmap_validate(v,n_bits) \
  clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))

/* low-level routine to remove trailing zeros from a bitmap */
always_inline uword *
_clib_bitmap_remove_trailing_zeros (uword * a)
{
  word i;
  if (a)
    {
      for (i = _vec_len (a) - 1; i >= 0; i--)
	if (a[i] != 0)
	  break;
      _vec_len (a) = i + 1;
    }
  return a;
}

/** Sets the ith bit of a bitmap to new_value.
    No sanity checking. Be careful.
    @param a - pointer to the bitmap
    @param i - the bit position to interrogate
    @param new_value - new value for the bit
    @returns the old value of the bit
*/
always_inline uword
clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
{
  uword i0 = i / BITS (a[0]);
  uword i1 = i % BITS (a[0]);
  uword bit = (uword) 1 << i1;
  uword ai, old_value;

  /* Removed ASSERT since uword * a may not be a vector. */
  /* ASSERT (i0 < vec_len (a)); */

  ai = a[i0];
  old_value = (ai & bit) != 0;
  ai &= ~bit;
  ai |= ((uword) (new_value != 0)) << i1;
  a[i0] = ai;
  return old_value;
}

/** Sets the ith bit of a bitmap to new_value
    Removes trailing zeros from the bitmap
    @param ai - pointer to the bitmap
    @param i - the bit position to interrogate
    @param value - new value for the bit
    @returns the old value of the bit
*/
always_inline uword *
clib_bitmap_set (uword * ai, uword i, uword value)
{
  uword i0 = i / BITS (ai[0]);
  uword i1 = i % BITS (ai[0]);
  uword a;

  /* Check for writing a zero to beyond end of bitmap. */
  if (value == 0 && i0 >= vec_len (ai))
    return ai;			/* Implied trailing zeros. */

  clib_bitmap_vec_validate (ai, i0);

  a = ai[i0];
  a &= ~((uword) 1 << i1);
  a |= ((uword) (value != 0)) << i1;
  ai[i0] = a;

  /* If bits have been cleared, test for zero. */
  if (a == 0)
    ai = _clib_bitmap_remove_trailing_zeros (ai);

  return ai;
}

/** Gets the ith bit value from a bitmap
    @param ai - pointer to the bitmap
    @param i - the bit position to interrogate
    @returns the indicated bit value
*/
always_inline uword
clib_bitmap_get (uword * ai, uword i)
{
  uword i0 = i / BITS (ai[0]);
  uword i1 = i % BITS (ai[0]);
  return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
}

/** Gets the ith bit value from a bitmap
    Does not sanity-check the bit position. Be careful.
    @param ai - pointer to the bitmap
    @param i - the bit position to interrogate
    @returns the indicated bit value, or garbage if the bit position is
    out of range.
*/
always_inline uword
clib_bitmap_get_no_check (uword * ai, uword i)
{
  uword i0 = i / BITS (ai[0]);
  uword i1 = i % BITS (ai[0]);
  return 0 != ((ai[i0] >> i1) & 1);
}

always_inline uword
clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
{
  uword i0 = i / BITS (ai[0]);
  uword i1 = i % BITS (ai[0]);
  ASSERT (i1 + n_bits <= BITS (uword));
  return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
}

/** Gets the ith through ith + n_bits bit values from a bitmap
    @param bitmap - pointer to the bitmap
    @param i - the first bit position to retrieve
    @param n_bits - the number of bit positions to retrieve
    @returns the indicated range of bits
*/
always_inline uword
clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
{
  uword i0, i1, result;
  uword l = vec_len (bitmap);

  ASSERT (n_bits <= BITS (result));

  i0 = i / BITS (bitmap[0]);
  i1 = i % BITS (bitmap[0]);

  /* Check first word. */
  result = 0;
  if (i0 < l)
    {
      result |= (bitmap[i0] >> i1);
      if (n_bits < BITS (bitmap[0]))
	result &= (((uword) 1 << n_bits) - 1);
    }

  /* Check for overlap into next word. */
  i0++;
  if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
    {
      n_bits -= BITS (bitmap[0]) - i1;
      result |=
	(bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
    }

  return result;
}

/** sets the ith through ith + n_bits bits in a bitmap
    @param bitmap - pointer to the bitmap
    @param i - the first bit position to retrieve
    @param value - the values to set
    @param n_bits - the number of bit positions to set
    @returns a pointer to the updated bitmap, which may expand and move
*/

always_inline uword *
clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
{
  uword i0, i1, l, t, m;

  ASSERT (n_bits <= BITS (value));

  i0 = i / BITS (bitmap[0]);
  i1 = i % BITS (bitmap[0]);

  /* Allocate bitmap. */
  clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
  l = vec_len (bitmap);

  m = ~0;
  if (n_bits < BITS (value))
    m = (((uword) 1 << n_bits) - 1);
  value &= m;

  /* Insert into first word. */
  t = bitmap[i0];
  t &= ~(m << i1);
  t |= value << i1;
  bitmap[i0] = t;

  /* Insert into second word. */
  i0++;
  if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
    {
      t = BITS (bitmap[0]) - i1;
      value >>= t;
      n_bits -= t;
      t = bitmap[i0];
      m = ((uword) 1 << n_bits) - 1;
      t &= ~m;
      t |= value;
      bitmap[i0] = t;
    }

  return bitmap;
}

always_inline uword *
clfib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
{
  uword a0, a1, b0;
  uword i_end, mask;

  a0 = i / BITS (bitmap[0]);
  a1 = i % BITS (bitmap[0]);

  i_end = i + n_bits;
  b0 = i_end / BITS (bitmap[0]);

  clib_bitmap_vec_validate (bitmap, b0);

  /* First word. */
  mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
  mask <<= a1;

  if (value)
    bitmap[a0] |= mask;
  else
    bitmap[a0] &= ~mask;

  for (a0++; a0 < b0; a0++)
    bitmap[a0] = value ? ~0 : 0;

  if (a0 == b0)
    {
      word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
      mask = pow2_mask (n_bits_left);
      if (value)
	bitmap[a0] |= mask;
      else
	bitmap[a0] &= ~mask;
    }

  return bitmap;
}

/** Macro to iterate across set bits in a bitmap

    @param i - the current set bit
    @param ai - the bitmap
    @param body - the expression to evaluate for each set bit
*/
#define clib_bitmap_foreach(i,ai,body)					\
do {									\
  uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set;	\
  __bitmap_len = vec_len ((ai));					\
  for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++)		\
    {									\
      __bitmap_ai = (ai)[__bitmap_i];					\
      while (__bitmap_ai != 0)						\
	{								\
	  __bitmap_first_set = first_set (__bitmap_ai);			\
	  (i) = (__bitmap_i * BITS ((ai)[0])				\
		 + min_log2 (__bitmap_first_set));			\
	  do { body; } while (0);					\
	  __bitmap_ai ^= __bitmap_first_set;				\
	}								\
    }									\
} while (0)


/** Return the lowest numbered set bit in a bitmap
    @param ai - pointer to the bitmap
    @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
*/
always_inline uword
clib_bitmap_first_set (uword * ai)
{
  uword i;
  for (i = 0; i < vec_len (ai); i++)
    {
      uword x = ai[i];
      if (x != 0)
	return i * BITS (ai[0]) + log2_first_set (x);
    }
  return ~0;
}

/** Return the higest numbered set bit in a bitmap
    @param ai - pointer to the bitmap
    @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
*/
always_inline uword
clib_bitmap_last_set (uword * ai)
{
  uword i;

  for (i = vec_len (ai); i > 0; i--)
    {
      uword x = ai[i - 1];
      if (x != 0)
	{
	  uword first_bit;
	  count_leading_zeros (first_bit, x);
	  return (i) * BITS (ai[0]) - first_bit - 1;
	}
    }
  return ~0;
}

/** Return the lowest numbered clear bit in a bitmap
    @param ai - pointer to the bitmap
    @returns lowest numbered clear bit
*/
always_inline uword
clib_bitmap_first_clear (uword * ai)
{
  uword i;
  for (i = 0; i < vec_len (ai); i++)
    {
      uword x = ~ai[i];
      if (x != 0)
	return i * BITS (ai[0]) + log2_first_set (x);
    }
  return i * BITS (ai[0]);
}

/** Return the number of set bits in a bitmap
    @param ai - pointer to the bitmap
    @returns the number of set bits in the bitmap
*/
always_inline uword
clib_bitmap_count_set_bits (uword * ai)
{
  uword i;
  uword n_set = 0;
  for (i = 0; i < vec_len (ai); i++)
    n_set += count_set_bits (ai[i]);
  return n_set;
}

/** Logical operator across two bitmaps

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns ai = ai and bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_and (uword * ai, uword * bi);

/** Logical operator across two bitmaps

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns ai = ai & ~bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);

/** Logical operator across two bitmaps

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns ai = ai & ~bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
/** Logical operator across two bitmaps

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns ai = ai or bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_or (uword * ai, uword * bi);

/** Logical operator across two bitmaps

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns ai = ai xor bi. ai is modified, bi is not modified
*/
always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);

/* ALU function definition macro for functions taking two bitmaps. */
#define _(name, body, check_zero)				\
always_inline uword *						\
clib_bitmap_##name (uword * ai, uword * bi)			\
{								\
  uword i, a, b, bi_len, n_trailing_zeros;			\
								\
  n_trailing_zeros = 0;						\
  bi_len = vec_len (bi);					\
  if (bi_len > 0)						\
    clib_bitmap_vec_validate (ai, bi_len - 1);			\
  for (i = 0; i < vec_len (ai); i++)				\
    {								\
      a = ai[i];						\
      b = i < bi_len ? bi[i] : 0;				\
      do { body; } while (0);					\
      ai[i] = a;						\
      if (check_zero)						\
	n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);	\
    }								\
  if (check_zero)						\
    _vec_len (ai) -= n_trailing_zeros;				\
  return ai;							\
}

/* ALU functions: */
_(and, a = a & b, 1)
_(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
#undef _
/** Logical operator across two bitmaps which duplicates the first bitmap

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns aiDup = ai and bi. Neither ai nor bi are modified
*/
     always_inline uword *
     clib_bitmap_dup_and (uword * ai, uword * bi);

/** Logical operator across two bitmaps which duplicates the first bitmap

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns aiDup = ai & ~bi. Neither ai nor bi are modified
*/
     always_inline uword *
     clib_bitmap_dup_andnot (uword * ai, uword * bi);

/** Logical operator across two bitmaps which duplicates the first bitmap

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns aiDup = ai or bi. Neither ai nor bi are modified
*/
     always_inline uword *
     clib_bitmap_dup_or (uword * ai, uword * bi);

/** Logical operator across two bitmaps which duplicates the first bitmap

    @param ai - pointer to the destination bitmap
    @param bi - pointer to the source bitmap
    @returns aiDup = ai xor bi. Neither ai nor bi are modified
*/
     always_inline uword *
     clib_bitmap_dup_xor (uword * ai, uword * bi);

#define _(name)						\
  always_inline uword *					\
  clib_bitmap_dup_##name (uword * ai, uword * bi)	\
{ return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }

_(and);
_(andnot);
_(or);
_(xor);

#undef _

/* ALU function definition macro for functions taking one bitmap and an immediate. */
#define _(name, body, check_zero)			\
always_inline uword *					\
clib_bitmap_##name (uword * ai, uword i)		\
{							\
  uword i0 = i / BITS (ai[0]);				\
  uword i1 = i % BITS (ai[0]);				\
  uword a, b;						\
  clib_bitmap_vec_validate (ai, i0);			\
  a = ai[i0];						\
  b = (uword) 1 << i1;					\
  do { body; } while (0);				\
  ai[i0] = a;						\
  if (check_zero && a == 0)				\
    ai = _clib_bitmap_remove_trailing_zeros (ai);	\
  return ai;						\
}

/* ALU functions immediate: */
_(andi, a = a & b, 1)
_(andnoti, a = a & ~b, 1) _(ori, a = a | b, 0) _(xori, a = a ^ b, 1)
#undef _
/** Return a random bitmap of the requested length
    @param ai - pointer to the destination bitmap
    @param n_bits - number of bits to allocate
    @param [in,out] seed - pointer to the random number seed
    @returns a reasonably random bitmap based. See random.h.
*/
     always_inline uword *
     clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
{
  vec_reset_length (ai);

  if (n_bits > 0)
    {
      uword i = n_bits - 1;
      uword i0, i1;
      uword log2_rand_max;

      log2_rand_max = min_log2 (random_u32_max ());

      i0 = i / BITS (ai[0]);
      i1 = i % BITS (ai[0]);

      clib_bitmap_vec_validate (ai, i0);
      for (i = 0; i <= i0; i++)
	{
	  uword n;
	  for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
	    ai[i] |= random_u32 (seed) << n;
	}
      if (i1 + 1 < BITS (ai[0]))
	ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
    }
  return ai;
}

/** Return the next set bit in a bitmap starting at bit i
    @param ai - pointer to the bitmap
    @param i - first bit position to test
    @returns first set bit position at or after i,
    ~0 if no further set bits are found
*/
always_inline uword
clib_bitmap_next_set (uword * ai, uword i)
{
  uword i0 = i / BITS (ai[0]);
  uword i1 = i % BITS (ai[0]);
  uword t;

  if (i0 < vec_len (ai))
    {
      t = (ai[i0] >> i1) << i1;
      if (t)
	return log2_first_set (t) + i0 * BITS (ai[0]);

      for (i0++; i0 < vec_len (ai); i0++)
	{
	  t = ai[i0];
	  if (t)
	    return log2_first_set (t) + i0 * BITS (ai[0]);
	}
    }

  return ~0;
}

/** Return the next clear bit in a bitmap starting at bit i
    @param ai - pointer to the bitmap
    @param i - first bit position to test
    @returns first clear bit position at or after i
*/
always_inline uword
clib_bitmap_next_clear (uword * ai, uword i)
{
  uword i0 = i / BITS (ai[0]);
  uword i1 = i % BITS (ai[0]);
  uword t;

  if (i0 < vec_len (ai))
    {
      t = (~ai[i0] >> i1) << i1;
      if (t)
	return log2_first_set (t) + i0 * BITS (ai[0]);

      for (i0++; i0 < vec_len (ai); i0++)
	{
	  t = ~ai[i0];
	  if (t)
	    return log2_first_set (t) + i0 * BITS (ai[0]);
	}
    }
  return i;
}

/** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )

    uword * bitmap;
    rv = unformat ("%U", unformat_bitmap_list, &bitmap);

    Standard unformat_function_t arguments

    @param input - pointer an unformat_input_t
    @param va - varargs list comprising a single uword **
    @returns 1 on success, 0 on failure
*/
static inline uword
unformat_bitmap_list (unformat_input_t * input, va_list * va)
{
  uword **bitmap_return = va_arg (*va, uword **);
  uword *bitmap = 0;

  u32 a, b;

  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
    {
      int i;
      if (unformat (input, "%u-%u,", &a, &b))
	;
      else if (unformat (input, "%u,", &a))
	b = a;
      else if (unformat (input, "%u-%u", &a, &b))
	;
      else if (unformat (input, "%u", &a))
	b = a;
      else if (bitmap)
	{
	  unformat_put_input (input);
	  break;
	}
      else
	goto error;

      if (b < a)
	goto error;

      for (i = a; i <= b; i++)
	bitmap = clib_bitmap_set (bitmap, i, 1);
    }
  *bitmap_return = bitmap;
  return 1;
error:
  clib_bitmap_free (bitmap);
  return 0;
}

/** Format a bitmap as a string of hex bytes

    uword * bitmap;
    s = format ("%U", format_bitmap_hex, bitmap);

    Standard format_function_t arguments

    @param s - string under construction
    @param args - varargs list comprising a single uword *
    @returns string under construction
*/
static inline u8 *
format_bitmap_hex (u8 * s, va_list * args)
{
  uword *bitmap = va_arg (*args, uword *);
  int i, is_trailing_zero = 1;

  if (!bitmap)
    return format (s, "0");

  i = vec_bytes (bitmap) * 2;

  while (i > 0)
    {
      u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);

      if (x && is_trailing_zero)
	is_trailing_zero = 0;

      if (x || !is_trailing_zero)
	s = format (s, "%x", x);
    }
  return s;
}
#endif /* included_clib_bitmap_h */

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */