Monday, October 08, 2007

Ring Buffer

Character Ring Buffer

Character buffers are often useful in embedded systems for a variety of tasks. This article presents a suggested implementation, which you can download from the articles page.

  1. Typical Uses
  2. Interface
  3. Design
  4. Implementation
    1. buffer_put
    2. buffer_get
    3. buffer_size

Typical Uses

Ring buffers are often used in hardware drivers, for example in interrupt-driven UART and SPI. Another use for character buffers is 'task queues': tasks can be represented as non-zero characters and 'queued' in the buffer. An application program then pulls the next task from the buffer and runs the corresponding routine. This can be useful when dealing with asynchronous user input (for example, from buttons). Simple task queues can be used as part of a very basic operating system.

Design

The ring buffer design allows a 'circular queue' data structure to be implemented in a statically allocated array. Dynamic memory allocation is best avoided in most embedded systems in order to reduce code size and performance while ensuring that memory use is 'bounded'.

A queue can be implemented as an array, with each element storing one byte of data (typically a character). 'head' and 'tail' indexes keep track of buffer occupancy. The 'ring' is formed by allowing the indexes to 'wrap' around the end of the array back to the beginning. This is especially useful since these buffers are typically written to and read from at somewhat random times.

Interface

The buffer interface should provide some version of the following routines:

  • initialization - set the buffer up in an 'empty' state
  • 'put' - insert a character into the buffer
  • 'get' - remove a character from the buffer
  • 'size' - report the occupancy of the buffer

Implementation

Here is my implementation of the 'ring' buffer, which you can download from the articles page. We begin by defining a simple 'buffer' data structure to hold the buffer array and 'head' and 'tail' indexes. I have chosen to allow array sizes that are powers of 2 because it allows me to use bitwise operations rather than comparisons when 'wrapping' the head and tail. In this case, the BUFFER_BITS must not be larger than 8 (for a buffer size of 256).

struct buffer
{
   
unsigned char data[1<<BUFFER_BITS];
    uint8_t head
, tail;
};

There are many possibilities for how to use the head and tail pointers. In my implementation, I chose the following rules:

  1. head and tail start at 0, head == tail indicates an 'empty' buffer.
  2. to write to the buffer, advance the tail and write at its new location.
  3. to read from the buffer, advance the head and then read from it.
  4. the head and tail advance to the 'right'

The rules are somewhat arbitrary, as long as you follow them consistently and ensure that your scheme works. I suggest trying it out of a piece of paper before writing any code. My scheme results in one buffer position being 'wasted' due to rule 1 above.

buffer_put

The following function puts a byte into the buffer. Its first step is to attempt to advance the tail pointer, wrapping it if needed. An error code is returned if the next tail position would collide with the head (that is, the buffer is full).

char buffer_put( struct buffer  *b, char c )
{
   
/* buffer is full if the next tail pointer position is the position of the
     * head pointer */

   
if ( ( b->tail+1 == b->head ) ||
       
( b->head == 0 && ( (b->tail+ 1) & (1<<BUFFER_BITS ) ) )
     
)
       
return 0; /* failed to put */
   
if ( (++(b->tail)) & (1<<BUFFER_BITS) ) /* adjust the tail pointer */
        b
->tail = 0;
    b
->data[b-> tail] = c; /* put into buffer at tail */
   
return c;
}

This function takes advantage of the 2^n size of the buffer. The tail pointer will only have a '1' in the same position as the mask 1<<BUFFER_BITS if it has reached the value of the size of the buffer array. Since we start counting at 0, this means that the tail must be wrapped to 0 because it has exceeded the last allowed value. For example, in an 8-position buffer, an index may have values between 0 and 7. At 7, the next index is 0 rather than 8.

buffer_get

This function adjusts the head and then returns the byte found at its new position. The same 'wrapping' technique is used when moving the head index.

char  buffer_get( struct buffer *b ) 
{
   
if( b->head == b->tail ) /* buffer is empty: nothing to get */
       
return 0;
   
if( (++(b->head)) & (1<<BUFFER_BITS) ) /* adjust the head pointer */
        b
->head = 0;
   
return b->data[b-> head];
}

buffer_size

This function returns the occupancy of the buffer. The buffer is either empty (head == tail) or not. A non-wrapped buffer's size is simply the difference between the tail and head positions. A wrapped buffer's size is the opposite of that.

uint8_t buffer_size( struct buffer * b )
{
   
if( b ->head == b->tail )
       
return 0;
   
return b-> head < b->tail ?
        b
->tail - b->head : (1<< BUFFER_BITS) - b->head + b->tail;
}

Implement an UART Driver (cc)

Writing an Interrupt-Driven UART Driver

Generally speaking, a driver's purpose is to provide an application or operating system with an interface to hardware. In this case, we will discuss designing and writing a driver for the UART.

The code examples presented here are snippets from my driver for the Atmel AVR microcontroller. The buffer data structure and functions mentioned are available as well. You may download the complete driver from the articles page.

  1. Design
  2. Receiver
  3. Transmitter
  4. Buffers
  5. Interface
    1. putchar()
    2. puts()
    3. getchar()
  6. Interrupt Handlers
    1. Receiver Interrupt
    2. Transmitter Interrupt
  7. Initialization

Design

An interrupt-driven device such as a UART can be represented as a three-level design on top of the hardware: the interrupt handlers, buffers, and application interface. For the UART, the interrupt handlers that we are most interested in are for the 'receiver has data' event and the 'transmitter is empty' (and thus can accept more data) event. The application interface may be the familiar 'getchar()' and 'putchar()' routines.

The following figure shows the three software layers, arranged from left to right by their 'closeness' to the hardware:

design

Receiver

The receiver is a physical shift register into which data arrives. A UART receiver generally has the capacity to store one byte of data at a time. In interrupt-driven mode, the UART will generate some sort of 'receiver has data' interrupt when data arrives. Because a UART is asynchronous and data can arrive at any moment, the application code running on the processor may not be ready to deal with the data. In fact, the application will not actually need the data until a routine like 'getchar()' is explicitly called. However, the received byte will be overwritten by the next byte if it is left in the receiver data register.

The receiver interrupt handler, therefore, will read the newly arrived byte (step '1' in the figure above) and copy it into the receive buffer (step '2'). Whenever it is called in application code, 'getchar()' will read the next available character from the receive buffer.

Transmitter

The UART transmit side copies a byte into a physical shift register, from which a hardware state machine actually shifts the data to the outside world. The transmitter register typically can hold one byte at a time and therefore some amount of time must pass before the next byte of data may be written. The transmitter is considered to be ready for the next byte when it is empty (that is, the data from the register has been shifted out). The UART typically provides an interrupt for 'transmitter is empty', allowing the transmitter to be dealt with only when it is ready.

In order to free the application code from having to wait for the UART transmitter to be ready, a transmit buffer is provided. Calls to routines like 'putchar()' simply copy characters to the transmit buffer. When the 'transmitter is empty' interrupt occurs, the transmit interrupt handler will read the next byte from the transmit buffer (step '1' in the figure above) and copy it into the UART transmitter register (step '2').

Buffers

The buffers placed between the UART interrupt handlers and application interface can be identical in implementation. A typical approach is a 'ring' buffer (similar to a circular queue). Please see "Character Ring Buffer" for an explanation of the buffer and example code. The buffer data type and interface used in that article is used in the examples here.

The transmit and receive buffers should be accessible both interrupt handlers and interface routines that need access to them. This can be accomplished by declaring them in global scope. Additionally, they (along with any global variables used by an interrupt handler) should be declared 'volatile' to prevent problems introduced by compiler optimization.

Interface

This section suggests implementations for the typical 'putchar()', 'puts()' and 'getchar()' functions. The code is written in a generic manner with processor-specific tasks such as interrupt configuration abstracted away as macros that are assumed to be defined.

putchar()

The 'putchar()' routine simply takes a byte and stores it in the transmit buffer. Typically, it returns the byte that was passed to it or an error code. Assuming that 0x00 (character NULL) is not expected to be transmitted, 0 may be a good choice of error code. -1 is also often used. Here is an example:

int uart_putchar( char c  )
{
   
if( buffer_put( &transmit_buffer, c ) ) {
        UCSR0B
|= (1<<UDRIE0); /* enable TX interrupt */
       
return -1 ;
   
}
   
return c;
}

puts()

It is usually helpful to provide a 'put string' function along with 'putchar()' unless the C stdio library functions puts() and printf() are going to be available. The 'puts()' routine can either copy the string into the transmit buffer as part of the buffer interface or it can simply call 'putchar()' repeatedly for each byte in the string. Assuming that we are using the version of 'putchar()' presented here, an implementation of 'puts()' can be written like this:

int uart_puts( const char * s )
{
   
int i = 0;
   
   
while( *s != '\0' )
       
if( uart_putchar( *s ++ ) == 0 )
           
break;
       
else
            i
++;
   
return i;
}

Recall that a C string is a character array with a terminating 0x00 byte. This version of 'puts()' attempts to copy each byte in the string to the transmit buffer, returning the number of bytes that it was able to copy.

getchar()

There are two typical ways to implement 'getchar()': blocking and non-blocking. Occasionally, it is helpful to have both available. A blocking 'getchar()' will wait until there is data in the receive buffer, effectively halting the application program if no data is available. This is similar to console input in a shell application and is sometimes desirable. However, a blocking call may be inappropriate in, for example, a control system. A non-blocking 'getchar()' will instead return a status code in the event that no data was available. This allows the routine to be called without potentially halting application code.

A blocking 'getchar()' can be written like:

char getchar( void  )
{
   
while( buffer_size ( &receive_buffer ) == 0 ); /* wait for data, if none is available */
   
return buffer_get( &receive_buffer );
}

The caller, of course, can also check the buffer capacity before calling 'getchar()'. The non-blocking version can be written in several ways. A status code (such as 0x00 or -1) can be used, or 'getchar()' could take a pointer to the 'destination' character and return only status codes. A simple implementation taking a pointer and returning the status code can be:

char uart_getchar( char  *c )
{
   
if( buffer_size ( &receive_buffer ) > 0 ) {
       
*c = buffer_get ( &receive_buffer );
       
return 1;
   
}
   
return 0 ;
}

Interrupt Handlers

Implementation for interrupt handlers greatly depends on the processor that you are using. Suggested implementations of 'receiver has data' and 'transmitter is empty' are discussed here in a very generic manner. You should read your processor and toolchain documentation for the details. Additionally, processors differ in the way UART interrupts occur. Some processors provide individual interrupts for various UART events. Others provide one general 'UART event' interrupt, whose handler must first decide what event has occurred and then handle that event. This is normally done by checking a status register. In such cases, the 'read' of the status register usually clears the interrupt flag.

The 'receiver has data' interrupt handler usually just needs to read from the UART data register and write to the receive buffer. Similarly, the 'transmitter is empty' handler simply reads from the transmit buffer and writes to the UART data register. In the 'transmit' handler, it is often helpful to check the occupancy of the transmit buffer after performing the read and copy. When the transmit buffer is empty, the 'transmitter is empty' interrupt can be turned off as it is no longer needed until 'putchar()' is called again (and re-enables the interrupt). This prevents the 'transmit' interrupt from happening again when the last byte is shifted out but no new data is ready.

Receiver Interrupt

Here is an example of a receiver interrupt handler for the AVR:

ISR(USART_RX_vect) 
{
   
char temp;

   
/* receiver has data */
   
if( UCSR0A & (1<< RXC0) ) {
        temp
= UDR0;
        buffer_put
( &receive_buffer, temp );
   
}
}

Transmitter Interrupt

Here is an example of a transmitter interrupt handler for the AVR:

ISR(USART_UDRE_vect) 
{    
   
/* we have data to send */
   
if( buffer_size( &transmit_buffer.g ) > 0 ) {
        UDR0
= buffer_get( &transmit_buffer );
       
if( buffer_size( &transmit_buffer ) == 0 ) /* no more data to send */
            UCSR0B
&= ~(1<<UDRIE0); /* disable TX interrupt */
   
}
   
else
        UCSR0B
<= ~(1<<UDRIE0); /* disable TX interrupt */
}

This interrupt handler transmits a byte if the transmit buffer had any data. It then ensures that the "transmitter is empty" interrupt is disabled when there is no more data in the transmit buffer.

Initialization

One final piece of software that your driver should provide is an 'init' routine. This routine should ensure that the UART is ready to use. Typically it will:

  • initialize the transmit and receive buffers
  • enable the UART transmitter and receiver (and configure IO pins, if needed), configure the baud rate and other UART settings
  • enable the UART 'receiver has data' interrupt

The 'transmitter is empty' interrupt is typically not enabled during 'init' because it is not needed until 'putchar()' is called. Here is an example for the AVR:

 inline void uart_init( uint16_t brr )
{
   
/* set up buffers */
    buffer_init
( receive_buffer );
    buffer_init
( transmit_buffer );
   
   
/* set up UART */
    UBRR0L
= (uint8_t)brr ;
    UBRR0H
= brr>>8;
#ifdef UART_X2
    UCSR0A
|= (1<<U2X0);

Saturday, October 06, 2007

Keyboard Shortcuts of Gmail


What are the keyboard shortcuts?

Keyboard shortcuts help you save time since you never have to take your hands off the keyboard to use the mouse. You'll need a Standard 101/102-Key or Natural PS/2 Keyboard to use the shortcuts.

To turn these case-sensitive shortcuts on or off, click Settings, and then pick an option next to Keyboard shortcuts.

Shortcut Key Definition Action
c Compose Allows you to compose a new message. <Shift> + c allows you to compose a message in a new window.
/ Search Puts your cursor in the search box.
k Move to newer conversation Opens or moves your cursor to a more recent conversation. You can hit <Enter> to expand a conversation.
j Move to older conversation Opens or moves your cursor to the next oldest conversation. You can hit <Enter> to expand a conversation.
n Next message Moves your cursor to the next message. You can hit <Enter> to expand or collapse a message. (Only applicable in 'Conversation View.')
p Previous message Moves your cursor to the previous message. You can hit <Enter> to expand or collapse a message. (Only applicable in 'Conversation View.')
o or <Enter> Open Opens your conversation. Also expands or collapses a message if you are in 'Conversation View.'
u Return to conversation list Refreshes your page and returns you to the inbox, or list of conversations.
y Archive*
Remove from current view
Automatically removes the message or conversation from your current view.
  • From 'Inbox,' 'y' means Archive
  • From 'Starred,' 'y' means Unstar
  • From any label, 'y' means Remove the label
* 'y' has no effect if you're in 'Spam,' 'Sent,' or 'All Mail.'
m Mute Archives the conversation, and all future messages skip the Inbox unless sent or cc'd directly to you. Learn more.
x Select conversation Automatically checks and selects a conversation so that you can archive, apply a label, or choose an action from the drop-down menu to apply to that conversation.
s Star a message or conversation Adds or removes a star to a message or conversation. Stars allow you to give a message or conversation a special status.
! Report spam Marks a message as spam and removes it from your conversation list.
r Reply Reply to the message sender. <Shift> + r allows you to reply to a message in a new window. (Only applicable in 'Conversation View.')
a Reply all Reply to all message recipients. <Shift> +a allows you to reply to all message recipients in a new window. (Only applicable in 'Conversation View.')
f Forward Forward a message. <Shift> + f allows you to forward a message in a new window. (Only applicable in 'Conversation View.')
<Esc> Escape from input field Removes the cursor from your current input field.

<Ctrl> + s

Save draft

Holding the <Ctrl> key while pressing s when composing a message will save the current text as a draft. Make sure your cursor is in one of the text fields -- either the composition pane, or any of the To, CC, BCC, or Subject fields -- when using this shortcut.

Macintosh users should use <Cmd> + s.

#

Delete

Moves the conversation to Trash.

Combo-keys - Use the following combinations of keys to navigate through Gmail.

Shortcut Key Definition Action
<tab> then <Enter> Send message After composing your message, use this combination to send it automatically. (Supported in Internet Explorer and Firefox, on Windows.)
y then o Archive and next Archive your conversation and move to the next one.
g then a Go to 'All Mail' Takes you to 'All Mail,' the storage site for all mail you've ever sent or received (and have not deleted).
g then s Go to 'Starred' Takes you to all conversations you have starred.
g then c Go to 'Contacts' Takes you to your Contacts list.
g then d Go to 'Drafts' Takes you to all drafts you have saved.
g then i Go to 'Inbox' Returns you to the inbox.


Top 20 Tallest Buildings(CH)

全球最高建筑前20位排名


排名 建筑名称 层数 高度(米) 竣工年份

1: [台北] 台北101 101 508 2004

2: [吉隆坡] 佩特纳斯大厦 88 452 1996 (双子星)

3: [芝加哥] 西尔斯大厦 108 443 1974

4: [上海] 金茂大厦 88 421 1998

5: [香港] 国际金融中心第二期 88 415 2003

6 :[广州] 中信广场 80 391 1997

7: [深圳] 地王大厦 69 384 1996

8: [纽约] 帝国大厦 102 381 1931

9: [香港] 中环广场 78 374 1992

10: [香港] 中国银行大厦 72 369 1990

11: [杜拜] 阿联酉首领塔 54 355 2000

12: [高雄] 东帝士大厦 85 347 1997

13: [芝加哥] 阿摩珂大厦 83 346 1973

14: [香港] 中环中心 79 346 1998

15: [芝加哥] 约翰-汉考克大厦 100 344 1969

16: [杜拜] 阿拉伯塔酒店 60 321 1999

17 :[纽约] 克莱斯勒大厦 77 319 1930

18: [亚特兰大] 国家银行广场大厦 55 312 1992

19: [洛杉矶] 第一洲际世界中心 75 310 1990

20: [吉隆坡] 电信大厦 55 310 2001

Tuesday, October 02, 2007

Travel to Genting Malaysia

Took travel bus 707, we got Genting Malaysia, which lay on a hill. Enjoyed ourselves above clouds.
 
3 star hotel but the environment is not that good. we even dont have toothbrush to use.
 
theme park is a good place to enjoy...  called "fun at the peak"
 
and also, genting is famous for the casino, people above 21 years old can enter casino room.

Monday, October 01, 2007

Back from Malaysia

For the visa reason, i have to go to Malaysia for fewdays and back to singapore in order to stay here ligally.
I went to Genting together with girlfriend on 20, Sept.. We had nice days at Genting and Kula Lumpur.
 
Genting is a visit and play place on a hill. We enjoyed a life above cloud :). Oh, i must say that , there is a gambling place there ...
 
Another day we went to Kula Lumpur, and went accross streets together with citizens.
 
 
 

Tuesday, September 25, 2007

Friday, September 07, 2007

test pst

here is a test