-1
\$\begingroup\$

I need to make the following function time constant - I have already removed if statements and have written it down to one line in the loop.

    /******************/
    uint8_t dseed[54];  // only 0 and 1 like {0,1,0,1,1,1,0,0,1,0,...}
    uint8_t fecb[256];
    const unsigned char g[55] = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,...};
    /******************/

    memset(fecb,0,54*sizeof(uint8_t));
    for (int i = 255; i >= 0; i--) {
        int feedback = dseed[i] ^ fecb[53];
        for (int j = 53; j > 0; j--){
            fecb[j] = fecb[j - 1] ^ (feedback && g[j]);
        }
        fecb[0] = g[0] && feedback;
    }

The code in my eyes looks constant time but when I measure it, it is not. Cycles vary between 165k and 185k.

The assembly code contains a conditional jump.

  for (int i = PARAM_K - 1; i >= 0; i--) {               //PARAM_K = 256
  0xC0000556:   C5 04 3F 30  LEA       a4,0xFF
  0xC000055A:   7B 00 00 4C  MOVH      d4,0xC000
> 0xC000059A:   B0 F4        ADD.A     a4,-0x1
> 0xC000059E:   FD 70 47 00  LOOP      a7,0xC000062C  
> 0xC0000622:   B0 F4        ADD.A     a4,-0x1
> 0xC0000626:   FD 70 03 00  LOOP      a7,0xC000062C  
> 0xC000062A:   3C BC        J         0xC00005A2  
> 0xC000062C:   39 AF 37 00  LD.BU     d15,[a10]0x37
> 0xC0000630:   3C A1        J         0xC0000572  
> 0xC0000632:   00 A0        DEBUG     
> 0xC0000634:   3C D0        J         0xC00005D4  

        feedback = dseed[i] ^ fecb[LENGTH - PARAM_K - 1];        //LENGTH = 310
  0xC0000572:   D9 AF 38 00  LEA       a15,[a10]0x38
  0xC0000576:   30 4F        ADD.A     a15,a4
  0xC0000578:   08 05        LD.BU     d5,[a15]0x0
  0xC000057A:   C5 0F 34 00  LEA       a15,0x34
  0xC000057E:   C6 F5        XOR       d5,d15
  0xC0000580:   DA 35        MOV       d15,0x35
  0xC0000582:   DF 05 40 80  JNE       d5,0x0,0xC0000602  <----- JNE
> 0xC00005D4:   82 7F        MOV       d15,0x7                    |
> 0xC00005D6:   C5 0F 35 00  LEA       a15,0x35                   |
                                                                  |
            for (int j = LENGTH - PARAM_K - 1; j > 0; j--)        |
                fecb[j] = fecb[j - 1] ^ (feedback && g[j]);       |
  0xC0000586:   92 F2        ADD       d2,d15,-0x1                |
  0xC0000588:   01 22 00 36  ADDSC.A   a3,a2,d2,0x0               |
  0xC000058C:   14 33        LD.BU     d3,[a3]                    |
  0xC000058E:   10 23        ADDSC.A   a3,a2,d15,0x0              |
  0xC0000590:   02 2F        MOV       d15,d2                     |
  0xC0000592:   34 33        ST.B      [a3],d3                    |
  0xC0000594:   FC F9        LOOP      a15,0xC0000586             |
> 0xC0000602:   60 4E        MOV.A     a14,d4           <---------|
> 0xC0000604:   92 F3        ADD       d3,d15,-0x1                
> 0xC0000606:   10 E6        ADDSC.A   a6,a14,d15,0x0
> 0xC0000608:   01 23 00 56  ADDSC.A   a5,a2,d3,0x0
> 0xC000060C:   10 23        ADDSC.A   a3,a2,d15,0x0
> 0xC000060E:   0C 60        LD.BU     d15,[a6]0x0
> 0xC0000610:   14 52        LD.BU     d2,[a5]
> 0xC0000612:   8B 0F 20 F2  NE        d15,d15,0x0
> 0xC0000616:   C6 2F        XOR       d15,d2
> 0xC0000618:   2C 30        ST.B      [a3]0x0,d15
> 0xC000061A:   02 3F        MOV       d15,d3
> 0xC000061C:   FC F3        LOOP      a15,0xC0000602  

            fecb[0] = g[0] && feedback;
  0xC0000596:   8B 05 20 F2  NE        d15,d5,0x0
> 0xC000059C:   2C A2        ST.B      [a10]0x2,d15
> 0xC000061E:   8B 05 20 F2  NE        d15,d5,0x0
> 0xC0000624:   2C A2        ST.B      [a10]0x2,d15
    }

Is this conditional jump responsible for the varying #cycles? ´

I already tried to compile this code snipped using __attribute__((optimize("O0"))), and I also tried volatile int feedback. Using the volatile keyword, this JNE disappears, but the code still isn't executed in constant time (because of stalls when writing/reading memory maybe?). Cycles vary between 215k and 235k using the volatile keyword.

Can this code efficiently made constant time? Is there some conditional branch I am missing?

Thank you for any help

\$\endgroup\$

closed as off-topic by Toby Speight, Mast, IEatBagels, t3chb0t, Ludisposed Sep 27 '18 at 13:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – Toby Speight, Mast, IEatBagels, t3chb0t, Ludisposed
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ I'm not sure whether it will help, but have you tried unrolling the loop? \$\endgroup\$ – Mast Sep 27 '18 at 10:49
  • \$\begingroup\$ no because, the value of "feedback" depends on "fecb" which is assigned in the inner for-loop, so i cannot unroll it right? and it will be 13500 or more lines :/ \$\endgroup\$ – jonnyx Sep 27 '18 at 10:59
  • \$\begingroup\$ Not easily, but not impossible either. If it's really that critical to do optimize it might be worth a try. At the moment, I see a loop in a loop. That won't run in constant time. Take a good look at what constant time would mean. Since i is size(fecb) - 1 and j is size(dseed) - 1, execution time will be based on those sizes. \$\endgroup\$ – Mast Sep 27 '18 at 11:07
  • 1
    \$\begingroup\$ Anyhow, the way your question is phrased, it asks for an explanation of your code. We don't do well with explanations of your code. You wrote it, you should know why it does what it does. If performance of your code is an issue, please describe in some detail what it's supposed to do so we can provide proper feedback on your approach. Please take a look at the help center. \$\endgroup\$ – Mast Sep 27 '18 at 11:11
  • 1
    \$\begingroup\$ @firda, thank you!!!!!, I just checked and my code also runs through if using & instead of &&. then i checked the times - every run takes the same amount of cycles!! If you post an answer, I will accept it! Thank you \$\endgroup\$ – jonnyx Sep 27 '18 at 13:17
4
\$\begingroup\$

Operator && is short-circuit which means, that it can give the result based only on the first operand (if it is false, the result is false, no matter what value the second operand has).

Operator & is not short-circuit and always executes both operands and then combines them.

That appears to be crucial for the code: feedback && g[j] and g[0] && feedback.

\$\endgroup\$
  • \$\begingroup\$ Note that feedback && g[j] and feedback & g[j] do not compute to the same value. A functional equivalent is !!feedback & !!g[j] is the same - but may not be time constant. IAC, unclear what functionality OP wants here. \$\endgroup\$ – chux Sep 27 '18 at 21:03
  • 2
    \$\begingroup\$ @chux: Given the comment // only 0 and 1 like {0,1,0,1,1,1,0,0,1,0,...} and other signs (fecb[0] = g[0] && feedback; and fecb[j] = fecb[j - 1] ^ (feedback && g[j]);), it was not unreasonable to assume all are indeed ones or zeroes. Anyway, the mixing of binary operators (^ instead of !=) with logical ones (&& vs. &) is indeed strange as well as the mixture of types (char, uint8_t, int). \$\endgroup\$ – firda Sep 27 '18 at 21:27
  • \$\begingroup\$ Yes, using only 0 and 1 make a & b and a && b functionally the same. \$\endgroup\$ – chux Sep 27 '18 at 21:35

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