[Feature request] Count leading/trailing zeros and population count

[aaaaaa123456789]

Having built-in functions to count the number of leading and trailing zeros in a number, as well as the number of set bits in it (population count), would be very useful, as this is something that is necessary every now and then and there's no way to do it without a loop.

Example:

  db CLZ(42), CTZ(42), POPCNT(42)

...would output 26, 1, 3. (The leading zero count is based on 32-bit numbers. This is easy to adjust to narrower widths by subtraction; the function doesn't need to worry about guessing the correct width.)

[ISSOtm]

What is it useful for?

[aaaaaa123456789]

To give an example I just came across, this ugly macro here: https://github.com/pret/pokecrystal/blob/b50dd57cbb8e163cd269255c8f754e5631760a03/macros/code.asm#L26-L48

That could be trivially rewritten as:

maskbits: MACRO
  if _NARG > 1
sh = \2
  else
sh = 0
  endc
  and (1 << (32 - CLZ((\1) - 1)) - 1) << sh
ENDM

[ISSOtm]

I don't think this is appropriate as a built-in function, then.

[aaaaaa123456789]

That case is a macro, but this would often be useful inline. And the truth is that there's no way to do this inline without invoking some sort of looping macro. The little example I posted in the chat is a great case of an inline use:

  if FOO & (FOO - 1)
    ; FOO is not a power of two
    ld a, c
    cp FOO
  else
    bit CTZ(FOO), c
  endc

There's simply no way of achieving that behavior right now, short of hiding the entire comparison code in a looping macro. And that's bad for several reasons.

[Rangi42]

With user-defined functions (#201) and a ternary operator (#621) (and STRFMT (#178) for terse CLZ and CTZ), these could be implemented as such (with adjustable width for CLZ and CTZ instead of assuming 32-bit):

DEF POPCNT(n) := n < 2 ? n : n % 2 + POPCNT(n / 2)
DEF CLZ(n) := n == 0 ? 32 : 32 - STRLEN(STRFMT("%b", n))
DEF CTZ(n) := n == 0 ? 32 : STRLEN(STRFMT("%b", n)) - STRRIN(STRFMT("%b", n), "1")
; closed-form expression from https://en.wikipedia.org/wiki/Bit_manipulation_instruction_set
DEF CTZ(n) := 31 + (!x) \
  - (((x & -x) & $0000FFFF) ? 16 : 0) \
  - (((x & -x) & $00FF00FF) ? 8 : 0) \
  - (((x & -x) & $0F0F0F0F) ? 4 : 0) \
  - (((x & -x) & $33333333) ? 2 : 0) \
  - (((x & -x) & $55555555) ? 1 : 0)

[Rangi42]

Also useful for counting the bits needed to store a number:

DEF CEIL_LOG2(n) := n == 0 ? 0 : STRLEN(STRFMT("%b", n))
DEF CLZ(n) := 32 - CEIL_LOG2(n)

[aaaaaa123456789]

Converting a number to string just to count its digits is one of the oldest bad programming memes around...
That being said, I wonder how much it'd slow down a build that relied on these functions heavily.

[ISSOtm]

I'm not sure you'd need string conversion, either, but that might not be faster. Then again, we will see about that once #201 is implemented.

[Rangi42]

You could also do:

def POPCNT(x) = x ? 1 + POPCNT(x & (x - 1)) : 0
def  TZCNT(x) = x ? x % 2 ? 0 : 1 + TZCNT(x / 2) : 0
def  LZCNT(x) = x ? (x & 1<<31) ? 0 : 1 + LZCNT(x << 1) : 0

[Rangi42]

Macro Assembler AS has these as BITCNT, FIRSTBIT, and LASTBIT.

[Rangi42]

Assuming user-defined functions will support recursion, and that we implement a short-circuiting ternary operator, these can be defined as follows:

DEF popcnt(x) := x ? (1 + popcnt(x & (x - 1))) : 0
DEF ctz(x) := x ? ((x &        1 ) ? 0 : (1 + ctz(x >> 1))) : 0
DEF clz(x) := x ? ((x & (1 << 31)) ? 0 : (1 + clz(x << 1))) : 0

[Rangi42]

We've decided to add BITWIDTH (aka BITLENGTH) and TZCOUNT (aka CTZ, though we won't support aliases) functions. :)

Useful equivalences:

• FLOOR(LOG2(x)) == BITWIDTH(x) - 1
• CEIL(LOG2(x)) == BITWIDTH(x - 1)
• LZCOUNT(x) == 32 - BITWIDTH(x) (aka CLZ)
• FIRSTSET(x) == TZCOUNT(x) + 1 == BITWIDTH(x & -x) (aka FFS)
• LASTSET(x) == 31 - BITWIDTH(x) (aka FLS)

No plans to add POPCOUNT because we're not aware of use cases for it beyond checking for powers of 2 (POPCOUNT(x) == 1 would be shorter than x != 0 && x & (x - 1) == 0, especially when x is a long expression, but that's it).

Edit: This is an interesting list of use cases, none of which apply to GB ASM. :P

[Rangi42]

So, ways to check whether n is a power of 2:

• popcount(n) == 1 (if we had that)
• n != 0 && n & (n - 1) == 0
• bitwidth(n) - 1 == bitwidth(n - 1)
• bitwidth(n) - 1 == tzcount(n)

pokecrystal has this macro for checking it, which gets three uses:

MACRO assert_power_of_2
	assert (\1) & ((\1) - 1) == 0, "\1 must be a power of 2"
ENDM