Efficient (a XOR (b+1)) known (a XOR b) in C for the ChaCha algorithm

Question

I'm currently trying to improve my ChaCha algorithm implementation. Here's the my code (written in C):

#include <string.h> // memcpy
#include <stddef.h> // size_t
#include <stdint.h> // uint32_t

typedef uint32_t ChaChaSigma [4];
typedef uint32_t ChaChaKey [8];
typedef uint32_t ChaChaNonce [4];
typedef enum ChaChaStandard {
    kOriginal,
    kIetf
} ChaChaStandard;
typedef short ChaChaRounds;
typedef uint32_t ChaChaBlock [16];

typedef struct ChaChaMatrix {
    union {
        struct {
            ChaChaSigma sigma; // The costant used. Usually "expand 32-byte k".
            ChaChaKey key;     // The key used. Has to be hashed or padded by the user manually.
            ChaChaNonce nonce; // The nonce used. It's formed by a block counter and an iv.
        };
        uint32_t words [16];   // The words of the matrix. Used for raw access.
    };
    ChaChaStandard standard;
    ChaChaRounds rounds;
} ChaChaMatrix;

// trick to have default values
#define INIT_CHACHAMATRIX(...) ((ChaChaMatrix){ \
    .sigma = {0x61707865UL, 0x3320646eUL, 0x79622d32UL, 0x6b206574UL}, \
    .key = {0, 0, 0, 0, 0, 0, 0, 0}, \
    .nonce = {0, 0, 0, 0}, \
    .standard = kOriginal, \
    .rounds = 20, \
    __VA_ARGS__ \
})

uint32_t rotl32 (uint32_t n, short r) {
    return (n << r) | (n >> (32 - r));
}

void ChaChaStep (uint32_t x[16], size_t a, size_t b, size_t c, short r) {
    x[a] += x[b];
    x[c] = rotl32(x[c] ^ x[a], r);
}

void ChaChaQuarterRound (uint32_t x[16], size_t a, size_t b, size_t c, size_t d) {
    ChaChaStep(x, a, b, d, 16);
    ChaChaStep(x, c, d, b, 12);
    ChaChaStep(x, a, b, d,  8);
    ChaChaStep(x, c, d, b,  7);
}

void ChaChaVerticalRound (uint32_t x[16]) {
    ChaChaQuarterRound(x, 0, 4,  8, 12);
    ChaChaQuarterRound(x, 1, 5,  9, 13);
    ChaChaQuarterRound(x, 2, 6, 10, 14);
    ChaChaQuarterRound(x, 3, 7, 11, 15);
}

void ChaChaDiagonalRound (uint32_t x[16]) {
    ChaChaQuarterRound(x, 0, 5, 10, 15);
    ChaChaQuarterRound(x, 1, 6, 11, 12);
    ChaChaQuarterRound(x, 2, 7,  8, 13);
    ChaChaQuarterRound(x, 3, 4,  9, 14);
}

void ChaChaComputeBlock (ChaChaMatrix * matrix, ChaChaBlock * block) {
    memcpy(block, matrix, sizeof(uint32_t)*16);
    short i;
    for (i = 0; i < matrix->rounds; i+=2) {
        ChaChaVerticalRound(*block);
        ChaChaDiagonalRound(*block);
    }
    for (i = 0; i < 16; i++) {
        (*block)[i] += matrix->words[i];
    }
}

I'm still planning an implementation to increase the counter without having to deal with type cast and IETF/Original standards.

The second action performed on the matrix uses the variable part (the block counter, inside the nonce). Because this (usually) increases only by 1 unit every time I was wondering if there's a way to improve its XOR efficency.

I opened excel and plotted a grpah of BITXOR(314, i), i being the variable going from 0 to 999. The graph shows a nice pattern. Every 0x100*n (in other words: every 4 "big downward steps" by 0x40 units) it jumps. The pattern is similar to the XOR(0, ..., n) one (?)

My question are:

• Are there some efficient ways to calculate a XOR (b+1) known a XOR b? The pattern, to me, suggests that it might be possible, but I'm not smart enough to find a solution...
• Does it make sense to implement this tiny improvement?

PS: if the software engegneering stackexchange better fits the question format I can move it there :)

Answer 1

A small review

trying to improve my ChaCha algorithm implementation

static function

rotl32() is not a well defined function for rotating when the count is 0 (or 32). That does not matter here as rotl32(n, 0) is not used. Since the function is only correct for local usage, make it static to avoid other modules using this reduced purpose function.

// uint32_t rotl32 (uint32_t n, short r) {
static uint32_t rotl32 (uint32_t n, short r) {

Avoid magic numbers

Why 16 below? Why uint32_t?. One could look around code and eventuality see what memcpy() is doing, but how about some direct alternatives?:

void ChaChaComputeBlock (ChaChaMatrix * matrix, ChaChaBlock * block) {
  // memcpy(block, matrix, sizeof(uint32_t)*16);
  memcpy(block, matrix, sizeof *block);
  // or 
  *block = (ChaChaBlock){0};

Are there some efficient ways to calculate a XOR (b+1) known a XOR b? The pattern, to me, suggests that it might be possible, but I'm not smart enough to find a solution...

Perhaps, I do not see one now.
Some other small ideas:

int vs. short

A small inefficiency is using sub-int parameters/objects. int is usually the best size for crisp code.

// uint32_t rotl32 (uint32_t n, short r) {
uint32_t rotl32 (uint32_t n, int r) {

 // short i;
 int i;

const, restrict

Let the compiler know that matrix and block do not overlap.

Use const to allow for greater functional usage and potentially some select optimizations.

// void ChaChaComputeBlock (ChaChaMatrix * matrix, ChaChaBlock * block) {
void ChaChaComputeBlock (const ChaChaMatrix * restrict matrix, 
    ChaChaBlock * restrict block) {

Does it make sense to implement this tiny improvement?

Perhaps yes. Keep in mind Is premature optimization really the root of all evil? .