1

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?

3

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 Feb 4 at 6:37
  • @blabb yes, but a close vote based on duplicate/cross posting is not applicable :( – Nordwald Feb 4 at 8:36
  • @blabb Thank you for pointing this out.. Yes. But still, we received fantastic answers from different aspects and angles. – lllllllllllll Feb 4 at 13:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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