Understand the CPU cycles of x86 instruction bsr/bsf

Question

I am on the hook to analysis some "timing channels" of some x86 binary code. I am posting one question to comprehend bsf/bsr opcode.

So high-levelly, these two opcodes can be modeled as a "loop", which counts the leading and trailing zeros of a given operand. The x86 manual has a good formalization of these opcodes, something like the following:

IF SRC = 0
  THEN
    ZF ← 1;
    DEST is undefined;
  ELSE
    ZF ← 0;
    temp ← OperandSize – 1;
    WHILE Bit(SRC, temp) = 0
    DO
      temp ← temp - 1;
    OD;
    DEST ← temp;
FI;

But to my suprise, bsf/bsr instructions seem to have fixed cpu cycles. According to some documents I found here: https://gmplib.org/~tege/x86-timing.pdf, seems that they always take 8 CPU cycles to finish.

So here are my questions:

1. I am confirming that these instructions have fixed cpu cycles. In other words, no matter what operand is given, they always take the same amount of time to process, and there is no "timing channel" behind. I cannot find corresponding specifications in Intel's official documents.

2. Then why it is possible? Apparently this is a "loop" or somewhat, at least high-levelly. What is the design decision behind? Easier for CPU pipelines?

Answer 1

I've found a site which seems to indicate this was implemented as a loop when the instructions were introduced:

BSF scans forward across bit pattern (0-n) while BSR scans in reverse (n-0).

                             Clocks                 Size
    Operands         808x  286   386   486          Bytes

    reg,reg           -     -   10+3n  6-42           3
    reg,mem           -     -   10+3n  7-43          3-7
    reg32,reg32       -     -   10+3n  6-42          3-7
    reg32,mem32       -     -   10+3n  7-43          3-7

Thankfully, they seem to optimized it starting with 486 (1989). As you already noticed, they seem to have improved the run time even further. Indeed, the current Intel Optimization Manual lists it with pretty low fixed clock cycles (3+1).

There is a much more in detail answer on stackexchange