FIFO memory having a memory region modifiable during operation

Abstract

A FIFO memory having a modifiable memory region; the FIFO memory being configured as a linear memory and as a circular buffer; the FIFO memory having a state machine that contains a new base value and a new top value for definition of a memory region allocated in the future, the lower boundary of which region is defined by the new base value and the upper boundary of which is defined by the new top value, and the state machine is configured in such a way that in a read mode and/or a write mode of the FIFO memory, the allocated memory region of the FIFO memory is modifiable by shifting the base pointer to the new base value, and/or by shifting the top pointer to the new top value.

Claims

1. A FIFO memory, comprising: a modifiable memory region, the FIFO memory being configured as a linear memory, and as a circular buffer; and a state machine that includes a base pointer, a top pointer, a write pointer, and a read pointer, the FIFO memory containing a currently allocated memory region whose lower boundary is defined by the base pointer and whose upper boundary is defined by the top pointer, the write pointer defining a current write address and the read pointer defining a current read address, the state machine further including a new base value and a new top value for defining a memory region allocated in the future, a lower boundary of which region is defined by the new base value and an upper boundary of which is defined by the new top value; wherein in at least one of a read mode of the FIFO memory and a write mode of the FIFO memory, the state machine is configured to modify an allocated memory region of the FIFO memory by at least one of: for shifting the base pointer to the new base value when the new base value is at least as low as a location to which the read pointer is presently set: determining, in a first determination, whether a first condition, that a location to which the write pointer is presently set equals a current value of the top pointer, is satisfied; and performing the shifting of the base pointer to the new base value in response to a result of the first determination being that the first condition is satisfied; and for shifting the top pointer to the new top value when the new top value is at least as high as the location to which the write pointer is presently set: determining, in a second determination, whether a second condition, that the location to which the read pointer is presently set equals a current value of the base pointer, is satisfied; and performing the shifting of the top pointer to the new top value in response to a result of the second determination being that the second condition is satisfied.

2. The FIFO memory as recited in claim 1, wherein the FIFO memory has an unoccupied region in which no unread data are present, and the state machine is configured in such a way that a point in time selected for setting the base pointer to the new base value is one at which both a previous value of the base pointer and the new base value of the base pointer are located in the unoccupied region.

3. The FIFO memory as recited in claim 1, wherein the state machine is configured to modify the allocated memory region by, for shifting the top pointer to the new top value when the new top value is at least as high as the location to which the write pointer is presently set: determining, in the second determination, whether the second condition, that the location to which the read pointer is presently set equals the current value of the base pointer, is satisfied; and performing the shifting of the top pointer to the new top value in response to the result of the second determination being that the second condition is satisfied.

4. The FIFO memory as recited in claim 1, wherein the state machine is configured to modify the allocated memory region by, for shifting the base pointer to the new base value when the new base value is at least as low as low as the location to which the base pointer is presently set: determining, in the first determination, whether the first condition, that the location to which the write pointer is presently set equals the current value of the top pointer, is satisfied; and performing the shifting of the base pointer to the new base value in response to the result of the first determination being that the first condition is satisfied.

5. The FIFO memory as recited in claim 1, wherein the FIFO memory has an unoccupied region in which no unread data are present, and the state machine is configured in such a way that a point in time selected for setting is one at which both a previous value of the top pointer and the new top value of the top pointer are located in the unoccupied region.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a FIFO memory having an allocated memory region having a contiguous occupied region and a divided unoccupied region.

(2) FIG. 2 shows a FIFO memory having an allocated memory region having a divided occupied region and a contiguous unoccupied region.

(3) FIG. 3 shows a FIFO memory according to the present invention during operation, the read pointer rd=base and the top pointer top being capable of being shrunk or enlarged.

(4) FIG. 4 shows a FIFO memory according to the present invention during operation, the write pointer wr=top and the base pointer base being capable of being shrunk or enlarged.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

(5) As in the conventional implementation of a FIFO, the circular buffer is permanently allocated in a linear memory and its boundaries are defined by two address pointers base and top. There is furthermore an address pointer wr for the position starting at which new data elements can be inserted, and an address pointer rd for the position starting at which data elements can be read out. Upon initialization: 1. base is set to the bottom end of the memory region; and 2. top is set to the top end of the memory region. 3. The write pointer wr and the read pointer rd are set to base. New data elements are written into the memory at the current address of wr. 1. wr is then incremented; 2. when wr reaches the value top, wr is set to base (wraparound). Data elements are read out from the address rd. 1. rd is then incremented; 2. when rd reaches the value of top, rd is set to base (wraparound).

(6) FIG. 1 shows a FIFO memory having an allocated memory region having a contiguous occupied region and a divided unoccupied region, and shows a state machine 100 with pointers pointing to respective locations of the FIFO memory.

(7) FIG. 2 shows a FIFO memory having an allocated memory region having a divided occupied region and a contiguous unoccupied region, and shows the state machine 100 with pointers pointing to respective locations of the FIFO memory.

(8) The FIFO is characterized in that there exists in the memory region one part that contains current data and is thus occupied (shown with hatching in the Figures) and another part that is unoccupied (not hatched). Depending on the current position of the pointers wr and rd, the following situations can occur: 1. wr>rd: the occupied region is present contiguously in the memory region (FIG. 1). 2. wr<rd: the occupied region is subdivided into two parts, one at the lower end and one at the upper end of the memory region (FIG. 2). 3. wr=rd: in this special case the FIFO is empty and can be treated, in terms of further consideration, as if wr>rd.

(9) In order to enable the change in size or change in location of the FIFO, the address pointers new_base and new_top, which contain the target size or the new location of the FIFO after the change, are introduced according to the present invention (see FIG. 1).

(10) A change in the base and top memory region boundaries is only possible if the position of the new pointers new_base and new_top is located outside the occupied region. While data are being written into and read out from the FIFO, the unoccupied region shifts in the opposite direction from the occupied region. The algorithm is based on the fact that the point in time selected for the modification of the base and top pointers is one at which both the old and the new value of the pointer are located in the unoccupied region.

(11) It is generally possible to enlarge the FIFO. Shrinking it, however, is only possible if the fill level of the FIFO is lower than or equal to the new size of the FIFO. If the fill level is higher, it is then not possible to shrink the FIFO at that point in time. Possible embodiments for dealing with this case are described in variant 3.

(12) Modifying Top and/or Base 1. The request to modify top is conveyed by setting new_top to a value not equal to top. Alternatively or simultaneously, the modification of base is conveyed by setting new_base to a value not equal to base. 2. The reading and writing of data elements continues as previously. At each update of rd or wr the following check is made: IF (rd=base) (see FIG. 3) IF (new_top>wr): top is set to the value new_top OTHERWISE: not possible to modify top at this time. IF (wr=top) (see FIG. 4) IF (new_base<rd): base is set to the value of new_base OTHERWISE: not possible to modify base at this time. 3. The enlargement is complete when top=new_top and base=new_base.

(13) FIG. 3 shows a FIFO memory according to the present invention during operation, and shows the state machine 100 with pointers pointing to respective locations of the FIFO memory, where the read pointer rd=base and the top pointer top being capable of being shrunk or enlarged.

(14) Selecting the point in time for modifying top (when rd reaches the value base) ensures that the top region of the FIFO is unused and the new value of top does not disrupt the continuity of the FIFO contents. new_top1 and new_top2 show the cases of enlarging and shrinking top.

(15) Analogously thereto, selecting the point in time for modifying base ensures that the lower region of the FIFO is unused. FIG. 4 shows, in this connection, a FIFO memory according to the present invention during operation, and shows the state machine 100 with pointers pointing to respective locations of the FIFO memory, where the write pointer wr=op and the base pointer base being capable of being shrunk or enlarged.

(16) Variant 1 (Alternative to the Basic Variant)

(17) As an alternative to incrementing the pointers wr and rd, the FIFO can also be implemented with decrementing pointers. This is generally valid for any FIFO and also applies to this FIFO, although the points in time and the sequence of pointer updates must be correspondingly adapted.

(18) Variant 2 (Improvement of the Basic Variant)

(19) As compared with the simple control system (updating the pointer at the next wraparound), there is also the possibility of carrying out the update of the pointers immediately when certain conditions of the read and write pointers are met. What is relevant here in particular is whether the pointer wr is located below or above rd, i.e., whether valid data are stored beyond the wraparound region. 1. The request to modify top is conveyed by setting new_top to a value not equal to top.

(20) Alternatively or simultaneously, the modification of base is conveyed by setting new_base to a value not equal to base. 2. IF (wr>rd) IF (new_top>wr): top is set to the value of new_top IF (new_base<rd): base is set to the value of new_base
OTHERWISE: (revert to the basic variant).

(21) The writing and reading of data elements continues as previously. At each update of rd or wr the following check is made: IF (rd=base) IF (new_top>wr): top is set to the value new_top OTHERWISE: not possible to modify top at this time. IF (wr=top) IF (new base<rd): base is set to the value of new_base OTHERWISE: not possible to modify base at this time. 3. The enlargement is complete when top=new_top and base=new_base.

(22) An advantage of this variant is that when the conditions are met, a change in size can be completed more quickly.

(23) Variant 3 (Expansion of the Basic Variant or of Variants 1 and 2)

(24) It was indicated above that a shrinkage of the FIFO is only possible if the fill level of the FIFO is lower than or equal to the new size of the FIFO. If this is not the case, the following possibilities exist: 1. Instead of waiting for a successful shrinkage that may never occur, the algorithm can alternatively be configured so that at the next pass of the pointers the FIFO is shrunk less than requested, and the shrinkage achieved is reported back. 2. A sufficient number of old values in the FIFO are discarded until a shrinkage is possible. 3. No new values are written into the FIFO until the fill level is low enough to enable a shrinkage (discarding new values) 4. The shrinkage request persists until the fill level of the FIFO is low enough.

LIST OF REFERENCE CHARACTERS

(25) base base pointer top top pointer wr write pointer rd read pointer new_base new base value new_top new top value