optimized leading zero counter

[suarezvictor]

Implementation of leading zero counter without adders (only muxes and AND/OR gates)
Return is uint6_t (a zero value has 32-bit leading zeros)
tested 10 million times with random values and (1 << random) values for including the zero

//(C) 2021 Victor Suarez Rovere <suarezvictor@gmail.com>
//LICENSE: GPLv3

#include <stdio.h>
#include "bitregs.h"

uint6_t count0s(uint32_t a32)
{
  uint16_t a16;
  uint8_t   a8;
  uint4_t   a4;
  uint2_t   a2;
  uint2_t   a1;

  uint1_t b16 = (a32 >> 16) == 0; a16 = b16 ? (a32 >> 0) : a32 >> 16;
  uint1_t b8  = (a16 >>  8) == 0;  a8 =  b8 ? (a16 >> 0) : a16 >> 8;
  uint1_t b4  = ( a8 >>  4) == 0;  a4 =  b4 ? ( a8 >> 0) :  a8 >> 4;
  uint1_t b2  = ( a4 >>  2) == 0;  a2 =  b2 ? ( a4 >> 0) :  a4 >> 2;
  uint1_t b1  = ( a2 >>  1) == 0;  a1 =  b1 ? ( a2 >> 0) :  a2 >> 1;

  uint5_t r = (b16 << 4) | (b8 << 3) | (b4 << 2) | (b2 << 1) | b1;
  return (r == 31 && a1 == 0) ? (uint6_t)32 : (uint6_t)r;
}

int count0s_raw(uint32_t a)
{
  int r = 0;
  while((a & 0x80000000) == 0)
  {
    if(++r == 32) break;
    a <<= 1;
  }
  return r;
}

#include <stdlib.h> //for srand()/rand()
int main()
{
   srand(0);
   int minr=100, maxr=-1;
   for(int i = 0; i < 10*1000*1000; ++i)
   {
     uint32_t a = rand() & 1 ? rand() : (1ull << rand() % 33);
     int r0 = count0s(a);
     int r1 = count0s_raw(a);
     if(r1 != r0)
     {
       printf("a=0x%08X r0=%d r1=%d\n", a, (int)r0, (int)r1);
       printf("ERROR\n");
       break;
     }
     if(r0 < minr) minr = r0;
     if(r0 > maxr) maxr = r0;
   }
   printf("Max, min: %d,%d\n", maxr, minr);
   return 0;
}

[JulianKemmerer]

Comparing

#pragma MAIN_MHZ new_count0s 1.0
uint6_t new_count0s(uint32_t a32)
{
  uint16_t a16;
  uint8_t   a8;
  uint4_t   a4;
  uint2_t   a2;
  uint2_t   a1;

  uint1_t b16 = (a32 >> 16) == 0; a16 = b16 ? (a32 >> 0) : a32 >> 16;
  uint1_t b8  = (a16 >>  8) == 0;  a8 =  b8 ? (a16 >> 0) : a16 >> 8;
  uint1_t b4  = ( a8 >>  4) == 0;  a4 =  b4 ? ( a8 >> 0) :  a8 >> 4;
  uint1_t b2  = ( a4 >>  2) == 0;  a2 =  b2 ? ( a4 >> 0) :  a4 >> 2;
  uint1_t b1  = ( a2 >>  1) == 0;  a1 =  b1 ? ( a2 >> 0) :  a2 >> 1;

  uint5_t r = (b16 << 4) | (b8 << 3) | (b4 << 2) | (b2 << 1) | b1;
  return (r == 31 & a1 == 0) ? (uint6_t)32 : (uint6_t)r;
}
#pragma MAIN_MHZ orig_count0s 1.0
uint6_t orig_count0s(uint32_t a32)
{
  return count0s_uint32(a32);
}

new_count0s BAD NVM

+------+-----+------+
|      |Cell |Count |
+------+-----+------+
|1     |LUT6 |     6|
|2     |FDRE |    38|
+------+-----+------+

orig_count0s

+------+-----+------+
|      |Cell |Count |
+------+-----+------+
|1     |LUT1 |     1|
|2     |LUT2 |     4|
|3     |LUT4 |    11|
|4     |LUT5 |     7|
|5     |LUT6 |    15|
|6     |FDRE |    37|
+------+-----+------+

[JulianKemmerer]

Damn nvm
There was issue with bit widths

need to add casting like so

uint5_t r = ((uint5_t)b16 << 4) | ((uint4_t)b8 << 3) | ((uint3_t)b4 << 2) | ((uint2_t)b2 << 1) | (uint1_t)b1;

new_count0s

+------+-----+------+
|      |Cell |Count |
+------+-----+------+
|1     |LUT2 |     6|
|2     |LUT4 |    10|
|3     |LUT5 |     6|
|4     |LUT6 |    17|
|5     |FDRE |    38|
+------+-----+------+

[suarezvictor]

I think the workflow should be allways as this: 1-compile with a regular compiler and test (1 second) 2-pipelinec it, verilate, test 3-do synth This way you can catch errors. An interesting thing here is how a pass with a C compiler gives different results than with pipelineC. Doesn't seem good. Maybe at least pipelineC should know such bit operations are different than with C and give a warning or error. El mar., 26 oct. 2021 20:59, Julian Kemmerer ***@***.***> escribió:

…

Damn nvm There was issue with bit widths need to add casting like so uint5_t r = ((uint5_t)b16 << 4) | ((uint4_t)b8 << 3) | ((uint3_t)b4 << 2) | ((uint2_t)b2 << 1) | (uint1_t)b1; +------+-----+------+ | |Cell |Count | +------+-----+------+ |1 |LUT2 | 6| |2 |LUT4 | 10| |3 |LUT5 | 6| |4 |LUT6 | 17| |5 |FDRE | 38| +------+-----+------+ — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#39 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBHVWMRH2DRGHSJVHNWILDUI46HVANCNFSM5GXOA7TQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[JulianKemmerer]

Ive been doing something like

3-do synth
1-compile with a regular compiler and test (1 second)
2-pipelinec it, verilate, test

instead for now, stopping if step 3 (my first step) doesn't show better resources