How is your circular buffer?

Go To Last Post
7 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This is more of a c programming question than a GCC question, I have and implementation of circular buffer using simple arrays that works but I want to know is anyone else has an implementation that works better. Here is a code snippet that shows the buffer load and the transmit interrupt that reads the buffer. The thing I noticed is that the last byte is not used. The location pointed at when the tx_head is equal to 0x3f is not written to when tx_tail is 0x00.

The buffer size TXBUFSIZE = 0x3f, 64 bytes.

// Fill the buffer one character at time.

void tx_char( unsigned char c )
{
	UCSRB |= (1<<UDRIE); 			// turn on tx interrupt
	if(((txbuf_head + 1) & TXBUFSIZE) != txbuf_tail) { // If tx_buf is not full
		tx_buf[txbuf_head++] = c;	// put the character in the tx_buf
		txbuf_head &= TXBUFSIZE;	// wrap the pointer
	}
	else { 						//else, error, the buffer is full
		flags |= (1<<tx_buf_full); 
		PORTB = (uint8_t)~(1<<0); // turn on LED for troubleshooting
	}
}
// Tx interrupt that reads the buffer.

SIGNAL (SIG_UART_DATA) // ISR - UART transmit interrupt, vector11
{
	if( txbuf_head != txbuf_tail ) {	// if tx_buf has data
		UDR = tx_buf[txbuf_tail++];	// send a byte from tx_buf and move to next byte
		txbuf_tail &= TXBUFSIZE;		// wrap the pointer
	}
	else    						// no more data to send
		UCSRB &= ~(1<<UDRIE);		// turn off tx data register empty interrupt
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

feralbeagle wrote:

void tx_char( unsigned char c )
{
	UCSRB |= (1<<UDRIE); 			// turn on tx interrupt
	if(((txbuf_head + 1) & TXBUFSIZE) != txbuf_tail) { // If tx_buf is not full
		tx_buf[txbuf_head++] = c;	// put the character in the tx_buf
		txbuf_head &= TXBUFSIZE;	// wrap the pointer
	}
	else { 						//else, error, the buffer is full
		flags |= (1<<tx_buf_full); 
		PORTB = (uint8_t)~(1<<0); // turn on LED for troubleshooting
	}
}

Try to move Tx enabling to the end of function - buffer may stay unmodified when
signal is immediately triggered.

Best regards Jurek S.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you try to use the last byte in a circular buffer, you can't tell the difference between a full buffer and an empty one because in both cases the head and tail pointers are the same. It can be done with additional code/flags but generally is not worth it.

C.H.

C. H.
-------------------------------------------------------------------
It's only waste if you don't use it!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

In the else part of tx_char, if your application allows, you could simply wait for free buffer space, with something like 'while (full) do sleep()' (sleep will unblock on an interrupt). Then you'd have no "error to troubleshoot", but your application would get temporarly blocked, which can be bad or not.

Embedded Dreams
One day, knowledge will replace money.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

To the beagle:

What are your aims for your circular buffer code? As fast as possible? Completely bulletproof? Emulate putchar() behavior? Other?

Your routines are not bulletproof. Imagine what would happen if an interrupt occurred between any two machine instructions (not just C statements) of your tx_char() routine. In particular, the head and tail variables need to be protected even if 8 bits.

You might as well return a success/fail from your tx_char() for the calling routine to take care of the buffer full condition.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is my circular buffer routines. The ISR routine (newsample) is designed to take a word out of the buffers (>256word long) and stick them into the PWM. Hopefully you can work out what is going on, and modify it to suite your application.
The fillfifo routine puts data into the buffers.
The take routine determines if the fifo is not full or empty. The put routine determines if the fifo is full or not full. That is only the take routine can determine if the fifo is empty.

Fillfifo:
'written in ASM since this must be done as fast as possible.
'with 16000 samples per sec & 8 bits per channel & 2 channels, we have to move 32000 bytes per sec
'22.050ks/s & 16b/ch & 2 ch => 88kB/s which is about the limit.
'why fifo > 255 bytes? (= word pointers)
'It takes about 11ms (measured) to fill the 32k file buffer, so we must buffer at least 11ms worth of sound per channel.
'At 16ks/s = a buffer size of about 176. BUT if a fresh fat has to be loaded, it may take >30ms
'so a fifo > 500 is needed (= word pointers).
lds r16, {fifostatus}
cpi r16, &HFF
brne fillfifofill                                           'While fifo not full, fill it
ret                                                         'RETURN is here
Fillfifofill:
rcall Getsample                                             'comes back with fudged ch word in r16-r17
push r16
push r17                                                    'save just in case we have 2 channels
lds r18, {Numchannels}
cpi r18, 2                                                  'if we have 2 channels
brne fillfifomono                                           'skip getting ch2 byte
rcall Getsample                                             'comes back with fudged ch word in r16-r17
Fillfifomono:
mov r20, r16
mov r21, r17                                                'copy Ch2 word, in either case
pop r17
pop r16                                                     'pop Ch1 word in either case
lds r24, {putpointer}
lds r25, {putpointer+1}                                     'put pointer to r24-r25
adiw r24, 1                                                 'incument put pointer
ldi r18, fifosize_lo
ldi r19, fifosize_hi
cp r18, r24
cpc r19, r25                                                'compare with fifo size
brne fillfifonowrap
clr r24
clr r25                                                     'If we have reached end, then wrap
Fillfifonowrap:
lsl r24
rol r25                                                     'multiply by bytes per word (2) since the fifo contains words
Loadadr Ch1fifo(1) , X
add r26, r24
adc r27, r25                                                'add pointer to fifo address
st X+, r16                                                  'Store Ch1 lo
st X, r17                                                   'Store Ch2 hi
Loadadr Ch2fifo(1) , X
add r26, r24
adc r27, r25                                                'add pointer to fifo address
st X+, r20                                                  'Store Ch2 lo
st X, r21                                                   'store Ch2 hi
'Check For Full
lsr r25
ror r24                                                     'divide pointer by bytes per word (2)
sts {putpointer}, r24
sts {putpointer+1}, r25                                     'Store pointer
adiw r24, 1                                                 'incument put pointer again
'Fifo size still in r18-r19
cp r18, r24
cpc r19, r25                                                'compare with fifo size again
brne fillfifonowrap1
clr r24
clr r25
Fillfifonowrap1:
lds r18,{takepointer}
lds r19, {takepointer+1}                                    'Take pointer to r16-r17
cp r24, r18
cpc r25, r19                                                'compare take pointer with put pointer
ldi r16, 1                                                  'fifo not full
brne fillfifoend
ldi r16, &HFF                                               'fifo full indication
Fillfifoend:
sts {fifostatus}, r16
rjmp fillfifo

'***************************************************************
'New Sample Interrupt Service Routine
'***************************************************************
'Sticks a new sample into the Pulse Width Modulator compare registers, from fifos
'Updates take pointer and fifo status.
'This is called by interrupt, so all registers must stay un corrupted.
'With NoSave, must save used registers
Newsample:
push r16
in r16, sreg
push r16
push r17
push r18
push r24
push r25
push r26
push r27                                                    'Save used registers
lds r24, {takepointer}
lds r25, {takepointer+1}                                    'get take pointer
lsl r24
rol r25                                                     'multiply by bytes per word (2) since the fifo contains words
Loadadr Ch1fifo(1) , X
add r26, r24
adc r27, r25                                                'add takepointer to address
ld r16, X+                                                  'get the pwm lo byte
ld r17, X                                                   'get the pwm hi
!out ocr1bh, r17                                            'High register first for this 16 bit register, refer page 108
!out ocr1bl, r16                                            'Lo register next. The CH1fifo(takepointer) byte
Loadadr Ch2fifo(1) , X
add r26, r24
adc r27, r25                                                'add takepointer to address
ld r16, X+                                                  'get the pwm lo byte
ld r17, X                                                   'get the pwm hi
'Warning ocr3b outside "out" address range, use "sts" instead
sts Ocr3bh, r17                                             'High register first for this 16 bit register, refer page 108
sts Ocr3bl, r16                                             'Lo register next. The CH1fifo(takepointer) byte
lsr r25
ror r24                                                     'divide pointer by bytes per word (2)
adiw r24, 1                                                 'incrument takepointer
ldi r16, fifosize_lo
ldi r17, fifosize_hi
cp r24, r16
cpc r25, r17                                                'compare with fifosize
brne newsamplenowrap
clr r24                                                     'if we have reached fifo size, set takepointer back to 0
clr r25
Newsamplenowrap:
lds r16, {putpointer}
lds r17, {putpointer+1}                                     'put pointer to r16-r17
cp r16 , r24
cpc r17, r25                                                'compare take pointer and put pointer
ldi r18, 0                                                  'empty status and / or under run
breq newsamplenoupdateptr                                   'on next sample use the same PWM word if take pointer and put pointer are equal
ldi r18, 1                                                  'not full status. We just took a byte, so it is not full.
sts {takepointer}, r24
sts {takepointer+1}, r25                                    'Save new takepointer if no under run
Newsamplenoupdateptr:
sts {fifostatus}, r18                                       'Update fifo status 0 = fifo empty, 1= not full
pop r27                                                     'Restore used registers
pop r26
pop r25
pop r24
pop r18
pop r17
pop r16
!Out Sreg, r16
pop r16
reti
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for the food for thought. Bulletproof is the goal, and efficiency, and just good design. I do not have the confidence yet to judge good firmware design at least in my own code. I am still more of a hardware engineer (analog) but I really enjoy using microcontrollers to solve problems. The circular buffer seems like such a staple of the firmware diet that I want to understand a well designed one. -Bryan