Off-by-one bug in random effect selection (random8(lim) / random16(lim) calls)

[coderabbitai]

Description

A pre-existing off-by-one bug affects random effect selection throughout the codebase. When selecting a random effect ID, the code calls random8(strip.getModeCount() - 1) or random16(strip.getModeCount() - 1), which prevents the last valid effect ID from ever being randomly selected.

Root Cause

FastLED's random8(N) and random16(N) functions return values in the range [0, N) (exclusive upper bound). To randomly select from effect IDs 0 through count-1, the code should call random*(count), not random*(count - 1).

Affected Locations

• wled00/ir.cpp line 724 (currently random16(strip.getModeCount() - 1))
• Any other locations using similar patterns with random8(strip.getModeCount() - 1)

Context

This issue was identified during review of PR #270 (16-bit effect IDs migration). The bug exists in the baseline mdev code and is not introduced by PR #270. The PR preserves the existing behavior while widening effect IDs from 8-bit to 16-bit.

Backlinks

• PR: change effect IDs from 8bit to 16bit #270
• Discussion: change effect IDs from 8bit to 16bit #270 (comment)
• Requested by: @softhack007

[softhack007]

Before trying to fix anything, we should verify if "FastLED's random8(N) and random16(N) functions return values in the range [0, N) (exclusive upper bound)" is really true - I have some doubts about it.

[ewowi]

This reminds me of the map() discussion we had

[ewowi]

🤖

I still have doubts reading this ...

[softhack007]

even the source code of fastled is confusing

• random8/random16 without parameters is "inclusive"
  https://github.com/FastLED/FastLED/blob/master/src/lib8tion/random8.h#L44-L59

• random8/random16 with upper limit is "exclusive"
  https://github.com/FastLED/FastLED/blob/master/src/lib8tion/random8.h#L69-L95

[softhack007]

so looking at the code of fastLED:

• random8() and random16() without parameter are indeed "inclusive", max=255 and 65535 respectively
• if you use them with a max value or range - example random8(254) the result is exclusive, and it does not include the upper bound. In my example, random8(254) = 0...253, random8(255) = 0...254

that's due to the 8bit oriented code of fastLED - They use (random8() * limit) >>8 instead of (random8() * limit) /255 which would be the correct formula and it is "inclusive"

proof of "exclusive" behaviour
the fastled formula can be written in float
">>8" means "/256" ==> trunc( (random8() * limit ) / 256 )
re-arrange ==> trunc( limit * random8() * / 256 )
insert maximum for random8() = 255 ==> trunc( limit * 255 / 256 )
255/256 is less than 1
the result value "limit" cannot be achieved, due to truncation to next smaller integer.

On tiny 8bit microprocessors, >>8 is a bit faster than the correct /255.
On esp32 they are almost the same, because esp32 has "integer divide" instructions in hardware - also on chips without FPU.
So with esp32 ">>8" is 1 CPU cycle, while "/255" is 2 CPU cycles.

But working around the "exclusive" will need a few extra instructions if you want an "inclusive" result. So in that case the speed "win" is negative.

[softhack007]

A (constructed and invented) example:

• your legacy code effect = random8(max_effect+1) always worked (+1 to overcome "exclusive") - currently with max_effect = 254.
• sw update adds a new effect, and increases max_effect to 255
• now you do effect = random8(255+1) = random8(256) => uint8 wrap-around => random8(0) = 0.

if you want to stick with 8bit, your only chance is to write a wrapper like this

uint8_t xxRandom8(uint8_t inclusive_max) { return inclusive_max == 255 ? random8() : random8(inclusive_max+1); }

and replace random8(max_effect+1) with xxRandom8(max_effect)

--> ugly. The same principle applies to random16(limit).

[softhack007]

I still have doubts reading this ...

@ewowi so the AI answer is largely aligned with my understanding.

• random16() without parameter includes the maximum
• random16(NUM_LEDS) and random16(0,NUM_LEDS) will give you results between 0 and NUM_LEDS-1
• I cannot follow the AI statement "slightly less when N is close to the maximum"; a few examples look good
  • max random16(65533) => 65535 * 65533 / 65536 = 65532.00 => OK
  • max random16(65534) => 65535 * 65534 / 65536 = 65533.00 => OK
  • max random16(65535) => 65535 * 65535 / 65536 = 65534.00 => OK

the thing to be careful about is that random16() and random16(65535) are not the same.