FIFO implementation in C-CodePudding

I am analysing an Internet guide, where I fond code like that. Can somebody explain me the usage of ~ and & operators?

Thanks in advance

uint8_t tx_fifo_put(tx_dataType data)
{
/*Check if FIFO is full*/
    if((tx_put_itr - tx_get_itr) & ~(TXFIFOSIZE-1))
        {
            /*FIFO full - return TXFAIL*/
            return (TXFAIL);
        }

    /*Put data into fifo*/
    TX_FIFO[tx_put_itr & (TXFIFOSIZE - 1)] = data;
    /*Incerment itr*/
    tx_put_itr  ;
    return(TXSUCCESS);
}

CodePudding user response：

What the code does, is an obfuscated way to replace a more human readable code.

As a commenter wrote before me, the TX_FIFO[tx_put_itr & (TXFIFOSIZE - 1)] = data; loops the output. Also as it was mentioned in comments, the code is meant to have size being power of two.

I do not know why it is done so, for me TX_FIFO[tx_put_itr % TXFIFOSIZE] = data does the same, but more readable. Also, a person expects predicate checks to be before data access. At least it is my nature.

The (w - r) &~ size part is a way to check for (1)w < r and, (2) as an edge case, w being equal to FIFOSIZE and r being zero. Semantically it should have meant, that "if the write pointer points to boundary, and read pointer points to start of a buffer, we suggest that, for our data structure, next write could be an overflow."

Let us see some code, numbers and their binary representation.

let s = 8 - 1, in binary is 00000111 and negated is 11111000.
let w = 0, let r = 1.
now in binary w = 00000000, r = 00000001.
w - r = 11111111, logical and that with ~(8 - 1) and get some value, other then zero.

Continuing the logic for the w < r case, we get that any negative integer will produce some bits in the above. So this definitely gives true for the OP if code.

Now the w = r case can not commit bits to the boolean test.

And last case,

let s = 8,
let w = 8
let r = 0

  w - r      = 00001000
~(8 - 1)     = 11111000
(w - r) &~ 7 = 00001000

All other cases where w > r give zero.

CodePudding user response：

The two operators:

& is a bitwise and operator

~ is a bitwise complement operator

Now for the posted code it's important to notice that TXFIFOSIZE must have a value which is a power of 2, i.e. values like 2, 4, 8, 16, 32, ...

When that is true, the code:

TX_FIFO[tx_put_itr & (TXFIFOSIZE - 1)] = data;

is equivalent to:

TX_FIFO[tx_put_itr % TXFIFOSIZE] = data;

Notice that tx_put_itr is being incremented in such a way that it will take value higher than TXFIFOSIZE. So in order to get a valid array index the code must find the remainder of tx_put_itr with respect to TXFIFOSIZE.

So how does work? Why are the above lines equivalent?

Let's take a value as example.

Assume TXFIFOSIZE is 8 (2 to the power of 3)
So TXFIFOSIZE-1 is 7
7 is bitwise 00....00111
And when you do:
SOME_NUMBER & 00....00111
You keep the 3 least significant bits of SOME_NUMBER
And that is exactly the remainder of when diving by 8

So let's look at

if((tx_put_itr - tx_get_itr) & ~(TXFIFOSIZE-1))

It is equivalent to

if((tx_put_itr - tx_get_itr) >= TXFIFOSIZE)

So it checks for "FIFO full"

Again using an example it works like this:

Assume TXFIFOSIZE is 8 (2 to the power of 3)
So TXFIFOSIZE-1 is 7
7 is bitwise 00....00111
~7 is bitwise 11....11000
And when you do:
SOME_NUMBER & 11....11000
You clear the 3 least significant bits of SOME_NUMBER and keep the rest unchanged
So if the result is non-zero it means that the difference between 
tx_put_itr and tx_get_itr is 8 (or more).