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
    ZF ← 1;
    DEST is undefined;
    ZF ← 0;
    temp ← OperandSize – 1;
    WHILE Bit(SRC, temp) = 0
      temp ← temp - 1;
    DEST ← temp;

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?

1 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

  • the link points to a question by op it appears he cross posted
    – blabb
    Commented Feb 4, 2019 at 6:37
  • @blabb yes, but a close vote based on duplicate/cross posting is not applicable :(
    – Nordwald
    Commented Feb 4, 2019 at 8:36
  • @blabb Thank you for pointing this out.. Yes. But still, we received fantastic answers from different aspects and angles. Commented Feb 4, 2019 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.