Line data    Source code

       1             : /* SPDX-License-Identifier: Apache-2.0
       2             :  * Copyright(c) 2021 Cisco Systems, Inc.
       3             :  */
       4             : 
       5             : #ifndef included_vector_count_equal_h
       6             : #define included_vector_count_equal_h
       7             : #include <vppinfra/clib.h>
       8             : 
       9             : static_always_inline uword
      10             : clib_count_equal_u64 (u64 *data, uword max_count)
      11             : {
      12             :   uword count;
      13             :   u64 first;
      14             : 
      15             :   if (max_count <= 1)
      16             :     return max_count;
      17             :   if (data[0] != data[1])
      18             :     return 1;
      19             : 
      20             :   count = 0;
      21             :   first = data[0];
      22             : 
      23             : #if defined(CLIB_HAVE_VEC256)
      24             :   u64x4 splat = u64x4_splat (first);
      25             :   while (count + 3 < max_count)
      26             :     {
      27             :       u64 bmp;
      28             :       bmp = u8x32_msb_mask ((u8x32) (u64x4_load_unaligned (data) == splat));
      29             :       if (bmp != 0xffffffff)
      30             :         {
      31             :           count += count_trailing_zeros (~bmp) / 8;
      32             :           return count;
      33             :         }
      34             : 
      35             :       data += 4;
      36             :       count += 4;
      37             :     }
      38             : #else
      39             :   count += 2;
      40             :   data += 2;
      41             :   while (count + 3 < max_count && ((data[0] ^ first) | (data[1] ^ first) |
      42             :                                    (data[2] ^ first) | (data[3] ^ first)) == 0)
      43             :     {
      44             :       data += 4;
      45             :       count += 4;
      46             :     }
      47             : #endif
      48             :   while (count < max_count && (data[0] == first))
      49             :     {
      50             :       data += 1;
      51             :       count += 1;
      52             :     }
      53             :   return count;
      54             : }
      55             : 
      56             : static_always_inline uword
      57     1417972 : clib_count_equal_u32 (u32 *data, uword max_count)
      58             : {
      59             :   uword count;
      60             :   u32 first;
      61             : 
      62     1417972 :   if (max_count <= 1)
      63      185920 :     return max_count;
      64     1232049 :   if (data[0] != data[1])
      65        8138 :     return 1;
      66             : 
      67     1223906 :   count = 0;
      68     1223906 :   first = data[0];
      69             : 
      70             : #if defined(CLIB_HAVE_VEC512)
      71           0 :   u32x16 splat = u32x16_splat (first);
      72           0 :   while (count + 15 < max_count)
      73             :     {
      74             :       u32 bmp;
      75           0 :       bmp = u32x16_is_equal_mask (u32x16_load_unaligned (data), splat);
      76           0 :       if (bmp != pow2_mask (16))
      77           0 :         return count + count_trailing_zeros (~bmp);
      78             : 
      79           0 :       data += 16;
      80           0 :       count += 16;
      81             :     }
      82           0 :   if (count == max_count)
      83           0 :     return count;
      84             :   else
      85             :     {
      86           0 :       u32 mask = pow2_mask (max_count - count);
      87           0 :       u32 bmp =
      88           0 :         u32x16_is_equal_mask (u32x16_mask_load_zero (data, mask), splat) &
      89             :         mask;
      90           0 :       return count + count_trailing_zeros (~bmp);
      91             :     }
      92             : #elif defined(CLIB_HAVE_VEC256)
      93     1223906 :   u32x8 splat = u32x8_splat (first);
      94     7280442 :   while (count + 7 < max_count)
      95             :     {
      96             :       u32 bmp;
      97             : #ifdef __AVX512F__
      98     6439690 :       bmp = u32x8_is_equal_mask (u32x8_load_unaligned (data), splat);
      99     6439690 :       if (bmp != pow2_mask (8))
     100      383159 :         return count + count_trailing_zeros (~bmp);
     101             : #else
     102           0 :       bmp = u8x32_msb_mask ((u8x32) (u32x8_load_unaligned (data) == splat));
     103           0 :       if (bmp != 0xffffffff)
     104           0 :         return count + count_trailing_zeros (~bmp) / 4;
     105             : #endif
     106             : 
     107     6056536 :       data += 8;
     108     6056536 :       count += 8;
     109             :     }
     110      840751 :   if (count == max_count)
     111      151041 :     return count;
     112             : #if defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE)
     113             :   else
     114             :     {
     115      689710 :       u32 mask = pow2_mask (max_count - count);
     116      689710 :       u32 bmp =
     117      689710 :         u32x8_is_equal_mask (u32x8_mask_load_zero (data, mask), splat) & mask;
     118      689710 :       return count + count_trailing_zeros (~bmp);
     119             :     }
     120             : #endif
     121             : #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
     122           0 :   u32x4 splat = u32x4_splat (first);
     123           0 :   while (count + 3 < max_count)
     124             :     {
     125             :       u64 bmp;
     126           0 :       bmp = u8x16_msb_mask ((u8x16) (u32x4_load_unaligned (data) == splat));
     127           0 :       if (bmp != pow2_mask (4 * 4))
     128             :         {
     129           0 :           count += count_trailing_zeros (~bmp) / 4;
     130           0 :           return count;
     131             :         }
     132             : 
     133           0 :       data += 4;
     134           0 :       count += 4;
     135             :     }
     136             : #else
     137             :   count += 2;
     138             :   data += 2;
     139             :   while (count + 3 < max_count && ((data[0] ^ first) | (data[1] ^ first) |
     140             :                                    (data[2] ^ first) | (data[3] ^ first)) == 0)
     141             :     {
     142             :       data += 4;
     143             :       count += 4;
     144             :     }
     145             : #endif
     146           0 :   while (count < max_count && (data[0] == first))
     147             :     {
     148           0 :       data += 1;
     149           0 :       count += 1;
     150             :     }
     151           0 :   return count;
     152             : }
     153             : 
     154             : static_always_inline uword
     155             : clib_count_equal_u16 (u16 *data, uword max_count)
     156             : {
     157             :   uword count;
     158             :   u16 first;
     159             : 
     160             :   if (max_count <= 1)
     161             :     return max_count;
     162             :   if (data[0] != data[1])
     163             :     return 1;
     164             : 
     165             :   count = 0;
     166             :   first = data[0];
     167             : 
     168             : #if defined(CLIB_HAVE_VEC256)
     169             :   u16x16 splat = u16x16_splat (first);
     170             :   while (count + 15 < max_count)
     171             :     {
     172             :       u64 bmp;
     173             :       bmp = u8x32_msb_mask ((u8x32) (u16x16_load_unaligned (data) == splat));
     174             :       if (bmp != 0xffffffff)
     175             :         {
     176             :           count += count_trailing_zeros (~bmp) / 2;
     177             :           return count;
     178             :         }
     179             : 
     180             :       data += 16;
     181             :       count += 16;
     182             :     }
     183             : #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
     184             :   u16x8 splat = u16x8_splat (first);
     185             :   while (count + 7 < max_count)
     186             :     {
     187             :       u64 bmp;
     188             :       bmp = u8x16_msb_mask ((u8x16) (u16x8_load_unaligned (data) == splat));
     189             :       if (bmp != 0xffff)
     190             :         {
     191             :           count += count_trailing_zeros (~bmp) / 2;
     192             :           return count;
     193             :         }
     194             : 
     195             :       data += 8;
     196             :       count += 8;
     197             :     }
     198             : #else
     199             :   count += 2;
     200             :   data += 2;
     201             :   while (count + 3 < max_count && ((data[0] ^ first) | (data[1] ^ first) |
     202             :                                    (data[2] ^ first) | (data[3] ^ first)) == 0)
     203             :     {
     204             :       data += 4;
     205             :       count += 4;
     206             :     }
     207             : #endif
     208             :   while (count < max_count && (data[0] == first))
     209             :     {
     210             :       data += 1;
     211             :       count += 1;
     212             :     }
     213             :   return count;
     214             : }
     215             : 
     216             : static_always_inline uword
     217             : clib_count_equal_u8 (u8 *data, uword max_count)
     218             : {
     219             :   uword count;
     220             :   u8 first;
     221             : 
     222             :   if (max_count <= 1)
     223             :     return max_count;
     224             :   if (data[0] != data[1])
     225             :     return 1;
     226             : 
     227             :   count = 0;
     228             :   first = data[0];
     229             : 
     230             : #if defined(CLIB_HAVE_VEC512)
     231             :   u8x64 splat = u8x64_splat (first);
     232             :   while (count + 63 < max_count)
     233             :     {
     234             :       u64 bmp;
     235             :       bmp = u8x64_is_equal_mask (u8x64_load_unaligned (data), splat);
     236             :       if (bmp != -1)
     237             :         return count + count_trailing_zeros (~bmp);
     238             : 
     239             :       data += 64;
     240             :       count += 64;
     241             :     }
     242             :   if (count == max_count)
     243             :     return count;
     244             : #if defined(CLIB_HAVE_VEC512_MASK_LOAD_STORE)
     245             :   else
     246             :     {
     247             :       u64 mask = pow2_mask (max_count - count);
     248             :       u64 bmp =
     249             :         u8x64_is_equal_mask (u8x64_mask_load_zero (data, mask), splat) & mask;
     250             :       return count + count_trailing_zeros (~bmp);
     251             :     }
     252             : #endif
     253             : #elif defined(CLIB_HAVE_VEC256)
     254             :   u8x32 splat = u8x32_splat (first);
     255             :   while (count + 31 < max_count)
     256             :     {
     257             :       u64 bmp;
     258             :       bmp = u8x32_msb_mask ((u8x32) (u8x32_load_unaligned (data) == splat));
     259             :       if (bmp != 0xffffffff)
     260             :         return count + count_trailing_zeros (~bmp);
     261             : 
     262             :       data += 32;
     263             :       count += 32;
     264             :     }
     265             :   if (count == max_count)
     266             :     return count;
     267             : #if defined(CLIB_HAVE_VEC256_MASK_LOAD_STORE)
     268             :   else
     269             :     {
     270             :       u32 mask = pow2_mask (max_count - count);
     271             :       u64 bmp =
     272             :         u8x32_msb_mask (u8x32_mask_load_zero (data, mask) == splat) & mask;
     273             :       return count + count_trailing_zeros (~bmp);
     274             :     }
     275             : #endif
     276             : #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_MSB_MASK)
     277             :   u8x16 splat = u8x16_splat (first);
     278             :   while (count + 15 < max_count)
     279             :     {
     280             :       u64 bmp;
     281             :       bmp = u8x16_msb_mask ((u8x16) (u8x16_load_unaligned (data) == splat));
     282             :       if (bmp != 0xffff)
     283             :         return count + count_trailing_zeros (~bmp);
     284             : 
     285             :       data += 16;
     286             :       count += 16;
     287             :     }
     288             : #else
     289             :   count += 2;
     290             :   data += 2;
     291             :   while (count + 3 < max_count && ((data[0] ^ first) | (data[1] ^ first) |
     292             :                                    (data[2] ^ first) | (data[3] ^ first)) == 0)
     293             :     {
     294             :       data += 4;
     295             :       count += 4;
     296             :     }
     297             : #endif
     298             :   while (count < max_count && (data[0] == first))
     299             :     {
     300             :       data += 1;
     301             :       count += 1;
     302             :     }
     303             :   return count;
     304             : }
     305             : 
     306             : #endif