C: UART, ISR, circular FIFO buffer: sometimes sends bytes in wrong order

I am pulling my hair out with an intermittent bug. I am receiving and transmitting bytes asynchronously (on a PIC16F77) and have implemented a circular software FIFO buffer for receiving and transmitting, combined with an interrupt service routine that is triggered when a byte can be sent or has been received.

The problem is that sometimes the bytes to be transmitted are done so in the wrong order.

I would hugely appreciate either:

advice on debugging it, or
assistance spotting the problem in the code

Progress so far:

It seems it only happens when there are some bytes being received - however I have been unsuccessful narrowing it down further. I am not getting any underruns or overruns, AFAIK.
It works without problems when I alter send_char() to either: 1. bypass software buffer by waiting for space in hardware buffer, and putting the byte directly into it, or 2. put the byte into the software buffer, even if there is space in the hardware buffer.

The code: (See bottom of question for description of hardware variables)

unsigned volatile char volatile rc_buff[16];
unsigned char volatile rc_begin = 0;
unsigned char volatile rc_next_free = 0;
unsigned char volatile rc_count = 0;

unsigned volatile char volatile tx_buff[16];
unsigned char volatile tx_begin = 0;
unsigned char volatile tx_next_free = 0;
unsigned char volatile tx_count = 0;

__interrupt isr(){
    // If a character has arrived in the hardware buffer
    if (RCIF){
        // Put it in the software buffer
        if (rc_count >= 16) die(ERROR_RC_OVERFLOW);
        rc_buff[rc_next_free] = RCREG;
        rc_next_free = (rc_next_free + 1) % 16;
        rc_count++;
    }
    // If there is space in hardware FIFO, and interrupt
    // has been enabled because stuff in software FIFO needs to be sent.
    if (TXIE && TXIF){
        // Put a byte from s/w fifo to h/w fifo.
        // (Here, tx_count is always > 0 (in theory))
        TXREG = tx_buff[tx_begin];
        tx_count--;
        tx_begin = (tx_begin + 1) % 16;
        // If this was the last byte in the s/w FIFO,
        // disable the interrupt: we don't care
        // when it has finished sending.
        if(tx_count==0) TXIE = 0;
    }
}
void send_char(char c){
    // disable interrupts to avoid bad things happening
    di();
    // if the hardware buffer is empty,
    if (TXIF){
        // put a byte directly into the hardware FIFO
        TXREG = c;
    } else {
        // cannot send byte directly so put in the software FIFO
        if (tx_count >= 16) die(ERROR_TX_OVERFLOW);
        tx_buff[tx_next_free] = c;
        tx_next_free = (tx_next_free + 1) % 16;
        tx_count++;
        // Enable TX interrupt since it now has something
        // it needs to transfer from the s/w FIFO to the h/w FIFO
        TXIE = 1;
    }
    ei();
}
char get_char(){
    // wait for a byte to appear in the s/w buffer
    while (!rc_count) {
        // If the h/w buffer overflowed, die with error
        if (OERR) die(ERROR_RC_HW_OVERFLOW)
    }
    // disable interrupts to avoid bad things happening
    di();
    unsigned char c = rc_buff[rc_begin];
    rc_count--;
    rc_begin = (rc_begin + 1) % 16;
    ei();
    return c;
}
void send_str(const unsigned char * str){
    unsigned char char_idx = 0;
    // until we reach the end-of-string null character,
    while (str[char_idx]){
        // queue a character for sending
        send_char(str[char_idx++]);
    }
}

Description of hardware variables:

For reference, the following are the (volatile) variables mapped to hardware registers and flags:

RCIF // Read-only receive flag:  True == byte(s) are waiting in hardware receive FIFO
TXIF // Read-only transmit flag: True == there is space in the hardware transmit FIFO
RCREG // Read only: Holds the next byte from the hardware FIFO that has been received
TXREG // Write-only: Assigning a byte to this transfers the byte to the hardware transmit FIFO
TXIE // Read/Write: Enable transmit interrupt: True == trigger ISR when TX h/w FIFO has space
RCIE // Read/Write: Enable receive interrupt:  True == trigger ISR when RC h/w FIFO has a byte to be read

Also, the below are special inline functions that suspend/resume interrupts to keep multiple grouped operations atomic. (The ISR cannot be interrupted by anything, including other interrupts)

di() // suspend interrupts
ei() // re-enable interrupts

Solution

Hmmm. I think there is some logic missing in your program (I will only cover the send part, since the receiver part seems to be working?):

The interrupt routine gets triggered if there is space in the send hw FIFO. You then send out one single byte from the sw buffer, adjust the index and return (note that there might still be some bytes queued within the sw buffer after that).

Whenever you send a byte, you look for space in the HW fifo and put the byte directly there, if not, you queue it in the SW buffer.

The problem seems to me that you expect the interrupt routine to drain the software buffer before returning to send_char() which isn't necessarily the case. After returning from the interrupt, the next instruction will be fully executed (there is no interrupt in the middle of an instruction). If this next instruction is the di() in send_char(), this interrupt will not happen and there will still be bytes in the sw buffer that can only be sent later (too late).

I'd either rather enqueue the bytes into the sw buffer from send_char() instead of writing directly to the fifo from send_char() or additionally check for the sw buffer to be empty before accessing the hw fifo directly.