System and method for implementing a counter

A counter is provided which can be implemented in flash memory allowing longer life through fewer erasures. The counter is incremented using a method that minimizes bit transitions from 1 to 0. In one embodiment, the counter is implemented in m+n bits. The bits of the counter are grouped into a binary portion of the counter of m bits and a unary portion of the counter of n bits. In order to increment the counter, the unary portion of the counter is incremented first. When the unary portion of the counter reaches a specific value, the binary portion of the counter is incremented. This limits 1 to 0 bit transitions and allows a large range of unique values to be read from the counter. In another embodiment, two unary counters are formed, which dynamically change in size as the counter is incremented.

FIELD OF THE INVENTION

The present invention relates to counters, and more specifically, to the use of a counter in such a way as to reduce certain bit transitions in the cluster.

BACKGROUND OF THE INVENTION

In a computer system, a counter holds data and can increment and provide the value of the data upon request. For example, a counter may be implemented in a register which holds numbers from zero to 255. Upon request, the counter increments the number by 1, mod 255. Upon request, the counter reports the value of the number in the register. Depending on the use of the counter, different increments may be preferable. “Increments” may be mathematical operations other than addition; for example, a multiplication may be performed. Generally, a counter reports on counter data and allows the modification of the counter data in a predetermined way.

It may be desirable in some contexts to implement a counter in hardware in a computer system in order to present barriers to adversaries attempting to modify the counter. Counters have been implemented in flash memory. However a limitation of flash memory is that when data in flash memory is changed, any bit transitions from 1 to 0 will cause flash memory to need to be erased and rewritten. If all bits remain the same or transition from 0 to 1, then no erasure is required for the change. Conventionally, flash memory has a limited lifespan of 10,000 to 1,000,000 erasures.

Users prefer computer system components to have a long life. Additionally, while some portions of a computer system may be replaceable, for security reasons, a flash counter may be made more difficult or impossible to exchange, in order to combat improper use by an adversary. Thus, the life of a counter is even more important. There is a need for a flash memory counter with an improved lifespan.

Thus, there is a need for a counter implementation that properly addresses and satisfies heretofore unfilled needs in the art.

SUMMARY OF THE INVENTION

In view of the foregoing, the present invention provides systems and methods for an improved counter that improves counter longevity. The present invention provides a counter that reduces bit transitions from 1 to 0.

In one embodiment, an (m+n)-bit memory is provided. m bits of memory are used for a binary portion of a counter, and n bits of memory are used for a unary portion of the counter. The unary portion of the counter is incremented first. Whenever the unary portion of the counter reaches a predetermined value, the binary portion of the counter is incremented. Since the unary portion of the counter only uses 1 to 0 bit transitions every n increments, the number of increments that cause a bit transition from 1 to 0 is reduced. Since a portion of the counter uses binary, a space savings is achieved. In one embodiment of the invention, a method is provided for choosing values for m and n in the memory.

In other embodiments, other techniques for reducing bit transitions from 1 to 0 are used.

Other features of the invention are described below.

DETAILED DESCRIPTION OF THE INVENTION

Overview

A counter is provided in a memory of m+n bits. These bits are grouped into a binary portion of the counter of m bits and a unary portion of the counter of n bits. In order to increment the counter, the unary portion of the counter is incremented. When the unary portion of the counter reaches a specific value, the binary portion of the counter is incremented. Since the unary portion of the counter only uses 1 to 0 bit transitions every n increments, the number of increments that cause a bit transition from 1 to 0 is reduced. Since a portion of the counter is binary, a space savings is achieved.

Other counter configurations are also possible. For example, using alternate increment techniques may also reduce 1 to 0 bit transitions. A counter of p bits which counts from 0 to p−1 (p increments) in unary, then sets all but the first bit to 1, and counts from p to 2p−2 (p−1 increments) in unary with the rest of the bits, then sets all but the first two bits to 1 and counts from 2p−1 to 3p−4 (p−2 increments) in unary with the rest of the bits, etc., reduces bit transitions significantly.

Generally, according to the systems and methods of the invention, counters are provided using increment techniques to lower the number of 1 to 0 bit transitions per counter or per cell in a counter divided among a number of cells.

Exemplary Computing Environment

One of ordinary skill in the art can appreciate that a computer or other client or server device can be deployed as part of a computer network, or in a distributed computing environment. In this regard, the present invention pertains to any computer system having any number of memory or storage units, and any number of applications and processes occurring across any number of storage units or volumes, which may be used in connection with the present invention. The present invention may apply to an environment with server computers and client computers deployed in a network environment or distributed computing environment, having remote or local storage. The present invention may also be applied to standalone computing devices, having programming language functionality, interpretation and execution capabilities for generating, receiving and transmitting information in connection with remote or local services.

The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices. Distributed computing facilitates sharing of computer resources and services by direct exchange between computing devices and systems. These resources and services include the exchange of information, cache storage, and disk storage for files. Distributed computing takes advantage of network connectivity, allowing clients to leverage their collective power to benefit the entire enterprise. In this regard, a variety of devices may have applications, objects or resources that may utilize the techniques of the present invention.

Counters Using Reduced Number of 1 to 0 Bit Transitions

According to one embodiment of the present invention, a counter implemented in flash memory will use a counter increment function that reduces the bit transitions from 1 to 0. This will reduce the number of times the flash memory to need to be erased and rewritten and thereby increase the life of the counter. In one embodiment, the counter is implemented in a number of cells of flash memory that are separately erasable and rewritable. In this case, the counter increment function used should reduce the number of times separate flash memory cells are rewritten.

Embodiment Using Unary and Binary Portions

In order to implement the counter with a reduced number of bit transitions, in one embodiment, a counter with a unary portion and a binary portion is created.

Using unary counting instead of binary counting reduces the number of bit transitions from 1 to 0. Unary counting is a simple method of counting, which is illustrated in Table 1:

TABLE 1Unary Counting from 0 to 15decimalunary equivalent0000000000000000100000000000000120000000000000113000000000000111400000000000111150000000000111116000000000111111700000000111111180000000111111119000000111111111100000011111111111100001111111111112000111111111111130011111111111111401111111111111115111111111111111
As can be seen in Table 1, this method of counting is space intensive. In counting from 0 to 15, 15 bits are used. However, no bit transitions from 1 to 0 occur. In general, to count from 0 to n, n bits are used and zero bit transitions from 1 to 0 occur. Counting in binary is not as space intensive, as illustrated in Table 2:

TABLE 2Binary Counting from 0 to 15decimalbinary equivalent00000100012001030011401005010160110701118100091001101010111011121100131101141110151111
In binary, the numbers from 0 to 15 can be represented in 4 bits. However, a bit transition from 1 to 0 occurs every other increment. In general, m bits can represent 2mvalues.

According to the inventive technique, and as shown inFIG. 2, a counter200is provided in a memory of size n+m. In a preferred embodiment, the memory is a single memory unit. In alternate embodiments, the memory may be comprised of a number of memory units. The memory is divided into two portions, a unary portion of the counter210of n bits and a binary portion of the counter220of m bits. In a preferred embodiment, the n lowest-significant bits comprise the unary portion of the counter, and the m highest-significant bits comprise the binary portion of the counter. However, other arrangements of the bit groupings are contemplated in other embodiments of the invention. In one embodiment, the m lowest-significant bits comprise the binary portion of the counter and the n highest-significant bits comprise the unary portion of the counter. In one embodiment, the bits comprising each counter are not found consecutively in the counter.

Additionally, the invention has been described with reference to unary increment as the increment method for the first part of the counter and binary increment as the increment method for the second part. However, in alternate embodiments of the invention, any other increment method can be used for the first and second parts of the counter. In order to provide the benefits of the invention, the increment method for the first counter part must make fewer 1 to 0 bit transitions per increment (on average) than the increment method for the second part.

Calculation of the Counter Value

In one embodiment, in order to read the value of the counter, the binary portion220and the unary portion210of the counter are read. The value stored in the binary portion220multiplied by n+1. The value stored in the unary portion210is then read. The sum of these two values is the value stored in the counter can be determined. According to this embodiment of the invention, values for a counter where the first three bits of the counter store the binary portion and the last four bits of the counter store the unary portion are shown in Table 3:

Incrementing the Counter

As shown inFIG. 3, the counter receives a request for an increment300. The counter then increments the unary portion of the counter310. In a preferred embodiment of the invention, this increment is unary increment, modulo n+1, so that an increment to a unary portion in which all bits are 1 results in all bits being set to 0. If the unary portion of the counter has reached a specified value (decision step320), then the binary portion of the counter is incremented330. In a preferred embodiment of the invention, this increment is a binary increment modulo 2m, so that an increment to a binary portion in which all bits are 1 results in all for the unary portion of the counter triggering the binary increment is zero.

Calculation of Values for m and n

In some applications, it is desirable for the counter to last only through one cycle of all the possible value of the counters. This may be because the counter is being used for security purposes and duplicate values are disfavored.

The predicted lifespan of the counter may be measured in terms of bit transitions from 1 to 0. This would happen, for example, in the case of flash memory. If the binary portion of the counter is incremented upon rollover of the unary portion of the counter, then bit transitions will only occur every n increments. Therefore, where the lifespan of the counter is c bit transitions from 1 to 0, the number of increments that can occur during the lifespan is c*n.

At the same time, the number of values that can be represented by the counter is equal to the number of values that can be represented by the binary portion of the counter multiplied by the number of values that can be represented by the unary portion of the counter. The binary portion of the counter can represent 2mnumbers, since it represents all values from 0 through 2m−1. The unary portion of the counter can represent n+1 numbers, since it represents all values from 0 through n. Therefore, the total number of values that can be represented is 2m(n+1).

In order to produce a counter that has an expected lifespan equal to one cycle of all the possible values, then the user should choose values for m and n such that c*n≈2m(n+1).

Alternate Counter Increment Function

Another embodiment of the invention in which a counter increment function reduces bit transitions from 1 to 0 uses a different counter increment function. In this function, the counter is successively divided into two unary counters which change sizes as the counter is incremented. For a counter of p bits, first, the counter counts from 0 to p−1 in unary using the last p−1 bits and stores a 0 in bit p. When the counter reaches p−1, to increment the counter, bit p becomes a one bit unary counter, bit p−1 becomes a one bit separator, and bits1through p−2 become a unary counter. When the counter then counts from p to 2p−2. When the counter reaches 2p−2, to increment the counter, bits p and p−1 become a two bit unary counter, bit p−2 becomes a one bit separator, and bits1through p−3 become a unary counter. This proceeds until the separator is bit2. (p+2)(p−1)/2 unique values may be counted on this counter. Another embodiment adds into the pattern a count where all the bits are set to 1, and in that embodiment, (p+2)(p−1)/2+1 unique values may be represented, with only p−2 instances of erasure of the counters.

For p=7, this method is illustrated in Table 4, where the separator bit is indicated in bold:

TABLE 4Example of Dynamically Sized Unary Counter Increment and Valuescountervalue00000000000000110000011200001113000111140011111501111116100000071000001810000119100011110100111111101111112110000013110000114110001115110011116110111117111000018111000119111001120111011121111100022111100123111101124111110025111110126
This is another embodiment of an increment scheme that minimizes 0 to 1 transitions. Additionally, as the unary counter on the left of the counter grows, bits included in that counter portion will only transition from 1 to 0 one time.

As shown inFIG. 4, in step400, an increment request is received. In step410, the first counter is incremented. In step420, it is determined whether the first portion of the counter has reached a specified value. If it has not, the method waits for a new increment request. If, however, the first portion of the counter has reached a specified value, a bit is added to the second portion of the counter, a bit is removed from the first portion of the counter, and the second portion of the counter is incremented430. The increments for each portion happen simultaneously—when a new counter value has been determined, including a new value for both portions of the counter, if necessary, only then is the new value written into the memory which holds the counter.

If this scheme is used in a flash memory counter with more than one cell and the cells are assigned to represent different areas of the counter at different times, an improvement over the life of the flash memory may be realized. For example, the number of possible values may be divided by the number of cells of flash memory to determine transition counts, and the cells assigned a different portion of the counter at each transition count. In this way, bits on the right side of the counter, which must be erased and rewritten more often than those on the left side of the counter may be assigned to different cells, and the average life of the cells extended.

Determining Counter Expiration

If a flash cell is erased too often it becomes unreliable and write operations can cause unpredictable values to be written. In general, it is desirable that the users of the counter can determine if the counter has exceeded its lifetime, and is no longer be reliable. If the lifetime has a known lower bound for erasures, then the increment logic can simply refuse to increment beyond a certain value. Users of the counter can treat the ceiling value as evidence of counter expiration.

If counter lifetime is less deterministic or more precision is desired, in an alternate embodiment the increment operator can increment-then-read the counter value. If the counter value is not as expected, a separate “suspect” flag or bit that is associated with the counter can be set. Users of the counter can consult the “suspect” flag or bit to determine the trustworthiness of the currently reported value.

Conclusion

Herein a system and method for counter implementation. As mentioned above, while exemplary embodiments of the present invention have been described in connection with various computing devices and network architectures, the underlying concepts may be applied to any computing device or system in which it is desirable to create a counter. Thus, the techniques for creating a counter in accordance with the present invention may be applied to a variety of applications and devices. For instance, the techniques of the invention may be applied to the operating system of a computing device, provided as a separate object on the device, as part of another object, as a downloadable object from a server, as a “middle man” between a device or object and the network, as a distributed object, etc. While exemplary names and examples are chosen herein as representative of various choices, these names and examples are not intended to be limiting.

The methods and apparatus of the present invention may also be practiced via communications embodied in the form of program code that is transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via any other form of transmission, wherein, when the program code is received and loaded into and executed by a machine, such as an EPROM, a gate array, a programmable logic device (PLD), a client computer, a video recorder or the like, or a receiving machine having the signal processing capabilities as described in exemplary embodiments above becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code combines with the processor to provide a unique apparatus that operates to invoke the functionality of the present invention. Additionally, any storage techniques used in connection with the present invention may invariably be a combination of hardware and software.

While the present invention has been described in connection with the preferred embodiments of the various figures, it is to be understood that other similar embodiments may be used or modifications and additions may be made to the described embodiment for performing the same function of the present invention without deviating therefrom. For example, while exemplary network environments of the invention are described in the context of a networked environment, such as a peer to peer networked environment, one skilled in the art will recognize that the present invention is not limited thereto, and that the methods, as described in the present application may apply to any computing device or environment, such as a gaming console, handheld computer, portable computer, etc., whether wired or wireless, and may be applied to any number of such computing devices connected via a communications network, and interacting across the network. Furthermore, it should be emphasized that a variety of computer platforms, including handheld device operating systems and other application specific operating systems are contemplated, especially as the number of wireless networked devices continues to proliferate. Still further, the present invention may be implemented in or across a plurality of processing chips or devices, and storage may similarly be effected across a plurality of devices. Therefore, the present invention should not be limited to any single embodiment, but rather should be construed in breadth and scope in accordance with the appended claims.