Compression of a set of integers

These present disclosure provides devices and techniques to compress a list of integers. A circuit may include a sorter to sort a list of integers and a subtractor to determine a range of integers represented in the list and to recursively subdivide the range into sub-ranges. The circuit may also include a bit determiner to determine an amount of information (e.g., bits) to use to add indications of the integers in the list to a compresses list information element based on the range and the sub-ranges.

TECHNICAL FIELD

Examples described herein are generally related to compression techniques and more specifically to compressing sets of integers for storage in computer-readable media.

BACKGROUND

Modern computing systems may store lists of data for various purposes. For example, a modern computing system may store a list of integers that represent bad blocks in a computer-readable media, such as, for example, bad blocks of a Solid State Drive (SSD). In some applications, it may be advantageous to compress these lists of integers. Using the SSD example, the SSD controller may maintain the list of bad blocks and store the list to a portion of memory reserved for this purpose. In order to maximize the memory storage efficiency, the list of bad blocks (e.g., represented by integers, or the like) can be compressed before storage.

DETAILED DESCRIPTION

As contemplated in the present disclosure, data can be compressed. Data compression refers to the process of reducing the amount of data needed to represent a given information. The underlying basis of the reduction process is the removal of redundant or unnecessary data. Data compression techniques reduce the costs for information storage and transmission and are used in many applications, ranging from simple file size reduction to speech and video encoding.

In particular, the present disclosure may be implemented to compress a set of integers. In some examples, the order of the integers in the set is random. In some examples, the order of the integers in the set does not matter, or the order can be determined from the contents of the set.

In general, an information element including indications of the set of integers is formed. With some examples, the information element comprises an indication of the set of integers using less information (e.g., bits, bytes, or the like) than an information element where the set of integers is indicated explicitly. Accordingly, the information element can be stored to a computer-readable memory storage location and may occupy less space than conventionally storing an information element with indications of the integers in the set. As such, resource usage may be reduced. Said differently, the present disclosure may be implemented to reduce the amount of space (e.g., in bytes, or the like) needed to store a set of integers.

In some examples, the present disclosure determines a range for integers in a set and stores an indication of this range to a compressed list information element. In some examples, the present disclosure defines the range based on a smallest and a largest integer of the set. For example, the present disclosure can sort the integers of the set and store an indication of the range. In some examples, the present disclosure may store an indication of the smallest integer and an indication of the largest integer to indicate the range. The present disclosure may recursively divide the range into sub-ranges by identifying a middle integer of each range or sub-range being divided. As used herein, the term “middle integer” may refer to the integer in the middle position of the range or sub-range being divided. This is explained in greater detail below.

For example, a first sub-range could be determined by identifying a first middle integer and defining the first sub-range based on the smallest integer and the first middle integer. Additionally, a second sub-range can be determined by defining the second sub-range based on the first middle integer and the largest integer. These first and second sub-ranges can themselves be subdivided by storing an indication of middle integers from each sub-range. In some examples, the present disclosure can store an indication of the identified middle integers based on the range or sub-range corresponding to the middle integer. With some examples, an indication of the middle integers may be stored using less information than required to explicitly store an indication of the middle integers. This is described in greater detail below.

Accordingly, the present disclosure provides techniques and apparatuses to determine a range of a set of integers and recursively subdivide the range into sub-ranges while indications of the integers are stored based on the range and/or sub-range to reduce an amount of information necessary to store the set of integers.

It is noted, the present disclosure can be implemented to compress sets of integers representing a variety of information. In particular, the present disclosure can be implemented to compress sets of integers representing, for example, bad blocks in a section of computer-readable memory, telephone numbers, Internet protocol (IP) addresses, license numbers, credit card numbers, passport numbers, hash values, license keys, a dictionary of unique symbols, floating point numbers of a fixed size (e.g., the significant may be represented as an integer, or the like), fixed point numbers of a fixed size, pixel locations, coordinates (e.g., x and y, Global Positioning System (GPS), latitude and longitude, or the like), strings of numbers, file system names, or the like. Examples are not limited to these contexts. Additionally, it is noted, the present disclosure often refers to examples where sets of integers are compressed. This is done for purposes of clarity and convenience only and not to be limiting.

Additionally, the present disclosure provides for retrieving the original set of integers of the compressed set. In general, the techniques to compress the set of integers are reversed to retrieve the original set of integers. More particularly, the position of known integers in the compressed set of integers can be used to determine an unknown integer. That is, the range and/or sub-range of integers can be used to retrieve a middle integer in the range, even where the middle integer is stored in a “compressed” form. This is explained in greater detail below.

FIGS. 1-3illustrate examples of a system to compress a set of integers, arranged according to at least some implementations of the present disclosure. In particular,FIG. 1depicts an example system100,FIG. 2depicts an example SSD200, andFIG. 3depicts an example circuit300. These figures are described separately from each other for purposes of convenience and clarity. However, it is noted, these figures occasionally use similar numeric designations. This is not to be limiting but is instead done for clarity of presentation.

Turning more specifically toFIG. 1, the system100is depicted. The system100may be made up, at least in part, of a processing component110, storage120, an interface130, input and/or output components140, or a display150. The storage120may include control routine122, a list information element124, and a compressed list information element126. The control routine122may include programming, logic, and/or features to cause the system100to perform various functions. For example, the control routine122may include instructions executable by the processing component to implement compression of a set of integers as described herein. Additionally, the control routine122may include an operating system or other programming to enable the host system to perform various functions. In some examples, the control routine122may be implemented as hardware, such as, for example, transistors, gates, registers, or the like, arranged to implement a particular function.

With some examples, the processing component110may include circuitry or processor logic, such as, for example, any of a variety of commercial processors. In some examples, the processing component110may include multiple processors, a multi-threaded processor, a multi-core processor (whether the multiple cores coexist on the same or separate dies), and/or a multi-processor architecture of some other variety by which multiple physically separate processors are in some way linked. Additionally, in some examples, the processing component110may include graphics processing portions and may include dedicated memory, multiple-threaded processing and/or some other parallel processing capability.

The storage120may include logic, a portion of which includes arrays of integrated circuits, forming non-volatile memory to persistently store data or a combination of non-volatile memory and volatile memory. It is to be appreciated, that the storage120may be based on any of a variety of technologies. In particular, the arrays of integrated circuits included in storage120may be arranged to form one or more types of memory, such as, for example, dynamic random access memory (DRAM), NAND memory, NOR memory, 3-Dimensional cross-point memory, ferroelectric memory, silicon-oxide-nitride-oxide-silicon (SONOS) memory, polymer memory such as ferroelectric polymer memory, ferroelectric transistor random access memory (FeTRAM or FeRAM), nanowire, phase change memory, magnetoresistive random access memory (MRAM), spin transfer torque MRAM (STT-MRAM) memory, or the like.

The system100may be operably coupled to another device (not shown) via the interface130. In general, the interface130may include logic and/or features to support a communication interface. For example, the interface130may include one or more interfaces that operate according to various communication protocols or standards to communicate over direct or network communication links. Direct communications may occur via use of communication protocols or standards described in one or more industry standards (including progenies and variants) such as those associated with the SMBus specification or the PCI Express specification. Network communications may occur via use of communication protocols or standards such those described in one or more Ethernet standards promulgated by the Institute of Electrical and Electronics Engineers (IEEE). For example, one such Ethernet standard may include Carrier sense Multiple access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications, published in December 2012 (hereinafter “IEEE 802.3-2012).

In some examples, the interface may facilitate communication over a bus, such as, for example, peripheral component interconnect express (PCIe), non-volatile memory express (NVMe), universal serial bus (USB), system management bus (SMBus), SAS (e.g., serial attached small computer system interface (SCSI)) interfaces, serial AT attachment (SATA) interfaces, or the like.

In various examples, the input and/or output components140may include one or more components to provide input to or to provide output from the system100. For example, the input and/or output components140may be a keyboard, mouse, joystick, microphone, track pad, speaker, haptic feedback device, touchscreen, or the like. In various embodiments, the display150may be based on any of a variety of displays (e.g., Plasma, LCD, LED, OLED, or the like) for displaying images and may include touch functionality.

In some examples, the interface130can receive the list information element124, such as, via an input stream. In general, the list information element126includes indications of a number of integers (e.g., refer toFIG. 4). It is noted, these integers are often collectively referred to herein as a set of integers, for example, the set of integers to be compressed. The processing component110may execute the control routine122to generate the compressed list information element126from the list information element124. In particular, the processing component110, in executing the control routine122, can generate the compressed list information element126including indications of the set of integers indicated in the list information element122, where the compressed list information element126may be smaller (e.g., in bits, or the like) than the list information element124(e.g., refer toFIG. 5).

In some examples, the processing component110, in executing the control routine122, can determine a range of the set of integers indicated by the list information element124. In particular, the processing component110, in executing the control routine122, can sort the set of integers based at least in part on a value of the integers and can determine a range of the set of integers by determining a smallest integer and a largest integer of the set.

The processing component110, in executing the control routine122, can add indications of the range of integers to the compressed list information element126. For example, the processing component, in executing the control routine122can add indications of the smallest integer and the largest integer to the compressed list information element126. In some examples, the smallest integer and largest integer are represented in the compressed list information element126explicitly. In some examples, the smallest integer is indicated in the compressed list information element126explicitly while a representation of the largest integer is indicated in the compressed list information element126. In some examples, the representation of the largest integer is based on the range.

The processing component110, in executing the control routine122, can recursively determine a number of sub-ranges of the set of integers. More specifically, the processing component110, in executing the control routine122, can subdivide the range into sub-ranges, by for example, determining a middle integer from the range and/or sub-ranges. In general, a middle integer can be determined by identifying the integers in the “middle” position, or the position located between the position of the lower bound and the position of the upper bound of the integers in the range or sub-range being divided. For example, a middle integer for the integers in position (1) and position (5) could be determined by identifying the integer in position (1+5)/2, or the integer in position3. This is explained in greater detail below.

The processing component110, in executing the control routine122, can add an indication of the middle integers to the compressed list information element126. In some examples, the processing component110, in executing the control routine122, can add an indication of a representation of the middle integers. With some examples, the representation of a middle integer is based on the range and/or sub-range of the middle integer. This is explained in greater detail below, for example, with respect toFIGS. 6-8.

In some examples, the processing component110, in executing the control routine122, can determine a set of integers (e.g., the list information element124) from a compressed representation of the set of integers (e.g., the compressed list information element126). In some examples, the processing component110, in executing the control routine122, can select positions in the compressed set of integers with known values. For example, as indicated above, the smallest integer and largest integer can be indicated explicitly in the compressed set of integers.

The processing component110, in executing the control routine122, can determine the position of an unknown integer (e.g., a middle integer, or the like) based on the range of these known integers. In particular, the processing component110, in executing the control routine122, can determine a number of bits in which the unknown integer is indicated from the range. Additionally, the processing component110, in executing the control routine122, can determine a position of the unknown integer in the set of integers and the value of the unknown integer from the range.

The processing component110, in executing the control routine122, can subsequently determine sub-ranges of known integers to recursively determine each of the unknown integers in the set of integers (e.g., each of the middle integers, or the like) from the position of the known integers. This is explained in greater detail below, for example, with respect toFIG. 9.

Turning more particularly toFIG. 2, the example SSD200is depicted. As noted, many of the same reference numerals are used inFIG. 2as were used inFIG. 1for purposes of convenience and clarity. However, this is not intended to be limiting and the SSD ofFIG. 2can be implemented with different components than the system100ofFIG. 1. The SSD may be made up, at least in part, of the processing component110, the storage120, or the interface130.

The storage120can include the control routine122, the list information element124, and the compressed list information element126. In general, the SSD200can compress a set of integers as described herein. In particular, the processing component110, in executing the control routine122, can generate the compressed list information element126from the list information element124.

Turning more specifically toFIG. 3, circuit300is depicted. As noted, many of the same reference numerals are used inFIG. 3as were used inFIG. 1for purposes of convenience and clarity. However, this is not intended to be limiting and the circuit300ofFIG. 3can be implemented with different components than the system100ofFIG. 1. The circuit300may be made up, at least in part, of logic301. The logic301may include any of a variety of hardware elements, such as, for example, arrays of integrated circuits implemented to perform a particular logical function. The logic can include an interface130, a sorter311, a subtractor313, and a bit determiner315.

In general, the logic301can generate the compressed list information element126from the list information element124. For example, the interface130can receive the list information element124, such as, via an input stream. The sorter311can sort the plurality of integers based at least in part on a value of the integers. The subtractor313can determine a range and a number of sub-ranges of the plurality of integers, for example, based on determining a difference between the integers. In particular, the subtractor311can determine middle integers corresponding to the range and/or sub-ranges. The bit determiner315can determine a representation of the integers in the set of integers, for example, based on the range and/or sub-range and can generate the compressed list information element124to include a representation of the integers indicated in the list information element124. Additionally, the interface130can output the compressed list information element126, for example, via an output stream.

In some examples, the logic301can generate the list information element124from the compressed list information element126. Said differently, the logic301can generate a set of integers from a compressed representation of the set of integers. For example, the interface130can receive the compressed list information element126, such as, via an input stream. The sorter311can identify known integers, or integers explicitly indicated in the compressed list.

The subtractor313can determine a range and a number of sub-ranges of the plurality of integers, for example, based on determining a difference between the known integers. In particular, the subtractor313can determine a position in the set of integers of the middle integers corresponding to the range and/or sub-ranges.

The bit determiner315can determine a value of the integers in the set of integers, for example, based on the range and/or sub-range and the position of the middle integers. In particular, the bit determiner315can determine a number of bits in which a representation of each middle integer is indicated in the compressed list information element126from the range and/or sub-range and can determine a value of the middle integer from the representation of the middle integers.

The interface130can output the set of integers as the list information element124, as a bit stream, or the like.

Any one or more of the system100, the SSD200, and/or the circuit300can be implemented as part of a host computing platform that may be, for example, a server, a server array or server farm, a web server, a network server, an Internet server, a work station, a mini-computer, a main frame computer, a supercomputer, a network appliance, a web appliance, a distributed computing system, multiprocessor systems, processor-based systems, or combination thereof. Accordingly, functions and/or specific configurations of system100, the SSD200and/or the circuit300described herein, may be included or omitted in various embodiments of system100, the SSD200, and/or the circuit300, as suitably desired.

The components and features of system100, the SSD200, and/or the circuit300may be implemented using any combination of discrete circuitry, application specific integrated circuits (ASICs), logic gates and/or single chip architectures. Further, the features of system100, the SSD200, and/or the circuit300may be implemented using microcontrollers, programmable logic arrays and/or microprocessors or any combination of the foregoing where suitably appropriate. It is noted that hardware, firmware and/or software elements may be collectively or individually referred to herein as “logic” or “circuit.”

It should be appreciated that the example system100, SSD200, and circuit300shown in the block diagram ofFIGS. 1-3may represent one structurally descriptive example of many potential implementations. Accordingly, division, omission or inclusion of block functions depicted in the accompanying figures does not infer that the hardware components, circuits, software and/or elements for implementing these functions would necessarily be divided, omitted, or included in examples.

FIGS. 4-5depict examples of the information elements described herein. In particular,FIG. 4depicts an example of the list information element124whileFIG. 5depicts an example of the compressed list information element126. It is noted, that these information elements may be stored, encoded, and/or formatted according to any of a variety of information standards. For example, the information elements may include various bits arranged to convey information with the element. That is, the information element may be arranged and encoded to convey information in a computing system, such as, for example, the system100, the SSD200, and/or the circuit300. In general, the information elements include a number of indications of information. These indications of information represented in the information element may be stored contiguously and/or non-contiguously in the information element. Examples are not limited in this context.

Turning more particularly toFIG. 4, the list information element124is depicted. The list information element124includes a number of indications of an integer410-a, where “a” is an integer greater than 1. For example, the list information element124is depicted including indications of an integer410-1,410-2,410-3,410-4,410-5,410-6,410-7, and410-8. Each of the indications of an integer includes a representation of an integer. In some examples, the indications410-ainclude an explicit representation of an integer. For example, the first indication of an integer410-1may represent the integer “14”. This may be represented in any of a variety of forms, such as, for example, hexadecimal, binary, or the like.

The list information element124, including indications410-arepresent a set of integers, which may be randomly distributed, whose order does not matter, and/or whose order can be determined from the set itself. For example, for purposes of explanation only, the first indication of an integer410-1may represent the integer 14; the second indication of an integer410-2may represent the integer 1; the third indication of an integer410-3may represent the integer 23; the fourth indication of an integer410-4may represent the integer 15; the fifth indication of an integer410-5may represent the integer 19; the sixth indication of an integer410-6may represent the integer 59; the seventh indication of an integer410-7may represent the integer 5; and the eighth indication of an integer410-8may represent the integer 44. Said differently, the list information element124may include indications of the following set [14, 1, 23, 15, 19, 59, 5, and 44].

The list information element124may include an indication of each integer explicitly using m bits. For example, for purposes of explanation only, the list information element124can include indications of the integers [14, 1, 23, 15, 19, 59, 5, and 44] using 6 bits to indicate each integer, for a total of 48 bits. For example, the list information element124can comprise binary indications [001110 000001 010111 001111 010011 111011 000101 101100] to indicate the set of integers. In some examples, the interface130could receive the list information element124via a bit stream, such as, the bit stream [001110 000001 010111 001111 010011 111011 000101 101100].

Turning more particularly toFIG. 5, the compressed list information element126is depicted. The compressed list information element126includes a number of indication of an integer510-a, where “a” is an integer greater than 1. In general, the compressed list information element126may include an indication of an integer510-afor each of the indications of integers410-ain the list information element124. For example, the compressed list information element126is depicted including indications of a smallest integer510-1, a largest integer510-2, and indications of middle integers510-3,510-4,510-5,510-6,510-7, and510-8. Each of the indications of an integer in the compressed list information124element may include a representation of one of the integers in the list information element124using no greater than m bits. In particular, using the example the list information element124given above where each integer is represented using 6 bits, the compressed list information element124can represent each of the integers using 6 or less bits. This is described in greater detail below. In particular, the present disclosure describes (e.g., refer toFIG. 6) an example compressed list information element126including indications of the example set of integers [14, 1, 23, 15, 19, 59, 5, and 44] discussed above. However, in general, the system100, SSD200, and/or circuit300can generate the compressed list information element126based at least on the following:Sort the integers indicated in the list information element, for example, from smallest to largest.Determine a range of the sorted set of integers based at least in part on identifying a smallest integer and a largest integer from the sorted set of integers.Add an indication of the smallest integer to the compressed list information element.Determine a representation RUof the largest integer, where RU=U−(L+n−1), and where U equals the largest integer, L equals the smallest integer, and n equals the number of integers in the sorted set of integers.Add an indication of the representation of the largest integer to the compressed list information element using log2[U−(L+n)] bits.Recursively sub-divide the range into sub-ranges by identify a middle integer of the range or sub-ranges.Determine, for each of the identified middle integers, a representation RMXof the middle integer, where RMx=Mx−LX−NX+2, and where MXequals the middle integer, LXequals the smallest integer of the range or sub-range being sub-divided, and NXequals the number of integers in the range or sub-range being sub-divided.Add, for each representation of a middle integer, an indication of the representation of the middle integer to the compressed list information element using log2[UX−(LX+NX+2)] bits, where UXequals the largest integer of the range or sub-range being sub-divided.

This is explained in greater detail below, for example, with respect toFIGS. 6-8. However, in general, the processing unit110, in executing the control routine122, can sort the set of integers from largest to smallest. In particular, the processing unit110, in executing the control routine122, can sort the integers410-1as [1, 5, 14, 15, 19, 23, 44, and 59]. The processing unit110, in executing the control routine122, can determine a range (e.g., smallest integer, largest integer) of the integers, for example, [1, 59]. The processing unit110, in executing the control routine can store an indication of the integers410-ain the list information element124based in part on the range [1, 59]. For example, the processing unit110, in executing the control routine122can store an indication of the smallest integer510-1(e.g., 1, or the like) and an indication of the largest integer510-2(e.g., 59, the representation RU, or the like) to the compressed list information element126. In some examples, an indication of the largest integer can be stored in the compressed list information element126using less than m bits (e.g., the number of bits used to store the indication in the list information element124). This is explained in greater detail below.

The processing unit110, in executing the control routine122can recursively sub-divide the range into sub-ranges. For example, the processing unit110, in executing the control routine122, can determine a first middle integer of the integers410-a. Said differently, the processing unit110, in executing the control routine110, can identify a middle integer of the range, and generate two sub-ranges based on the range and the middle integer. In general, the middle integer is the integer in the middle position, or the integer in the position between the position of the lower bound integer and the position of the upper bound integer of the range or sub-range being divided. The processing unit110, in executing the control routine122can determine a sub-range defined by the smallest integer and the middle integer and a sub-range defined by the middle integer and the largest integer.

Using the example integer set above, the processing unit110can determine a first middle integer as 19 and form two sub-sets of integers having a range of [1, 19] and [19, 59], respectively. In particular, the integer in the middle position between the position of the lower bound integer (e.g., position1) and the position of the upper bound integer (e.g., position8) is 4.5, which can be rounded up to identify the integer 19. As another example, the position could be rounded down, where the integer 15 could be identified as the middle integer. However, for purposes of convenience in discussing the present disclosure, it is assumed that the position of the integers is rounded up where needed.

The processing unit110, can divide the range [1, 59] into sub-ranges [1, 19] and [19, 59]. The processing unit110, in executing the control routine122, can store an indication of the first middle integer510-3(e.g., 19, RMX, or the like) to the compressed list information element126. In some examples, an indication of the middle integer can be stored in the compressed list information element126using less than m bits (e.g., the number of bits used to store the indication in the list information element124). This is explained in greater detail below.

The processing unit110, in executing the control routine122, can continue to recursively sub-divide these sub-ranges by identifying additional middle integers and defining additional sub-ranges based on the additional middle integers. In particular, the processing unit110, in executing the control routine122, can determine middle integers from each of the sub-ranges and store an indication of the middle integers to the compressed list information element126. For example, the processing unit110can add indications of middle integers510-4,510-5,510-6,510-7,510-8to the compressed list information element126. In some examples, the processing unit110can continue to determine middle integers and store indications of the middle integers until all integers in the set are represented in the compressed list126.

Additionally, although described in greater detail below (e.g., refer toFIG. 9,) the system100, SSD200, and/or circuit300can generate the list information element124from the compressed list information element126based at least on the following:Select a position PLof a first integer in the set of integers with a known value LX.Select a position PUof a second integer in the set of integers with known value UX.Determine a range corresponding to the first and second integers.Recursively sub-divide the range into sub-ranges by identifying a position of a middle integer of the range or sub-ranges.Determine, for each middle integer, a number of bits used to indicate a representation RMXof the middle integers with in the compressed list information element using log2[UX−(LX+NX+2)] bits, where NX=PU−PL+1.

Determine, for each middle integer, the value MXof the middle integer from the representation RMX, where Mx=RMx+LX+NX−2.

FIG. 6illustrates a technique600to compress a set of integers, according to at least some examples of the present disclosure. The technique600is discussed with reference to the circuit300ofFIG. 3, the list information element124ofFIG. 4, and the compressed list information element126ofFIG. 5. Additionally, the technique600is discussed with reference to the example set of integers [14, 1, 23, 15, 19, 59, 5, and 44] used above. However, it is noted the technique600can be implemented by any of the systems and/or devices discussed herein, such as, for example, the system100, the SSD200, the circuit300, or the like. Furthermore, the technique600can be implemented to generate a compressed representation of a set of integers of any size and/or values. Furthermore, binary encoding is used for the indications of integers in this example for purposes of convenience. However, this is not to be limiting and other encoding mechanisms, e.g., hexadecimal, or the like may be implemented. Examples are not limited in these contexts.

It is also worthy to note, the example given here in conjunction withFIG. 6does not have repeated integers in the set of integers. However, the present disclosure can be implemented to compress a set of integers where integers are repeated in the set. Furthermore, the example given here uses whole numbers in determining the number of bits to use to store an integer or integer representation. However, a fractional number of bits could be used to store an integer or integer representation. For example, an arithmetic encoding scheme could be employed to store indications of integers or integer representation as described herein using fractional numbers of bits. Examples are not limited in these contexts.

The technique600may begin at block 6.1. At block 6.1 the sorter311can receive the list information element124. For example, the sorter311can receive, via the interface130, the list information element124. The list information element124can include indications of integers (e.g.,410-a, or the like). For example, for purposes of discussion only, the list information element124can include indications of n integers [14, 1, 23, 15, 19, 59, 5, and 44], where n equals 8. These n integers may correspond to integer indications410-1to410-8of the list information element124.

As can be appreciated, each integer may be represented using m bits. For purposes of explanation, let m equal 6. The variables n and m are referenced below in discussing the determination of compressed representations of each of the integers. In some examples, the sorter311can receive the following bit stream [001110 000001 010111 001111 010011 111011 000101 101100] corresponding to the list information element124. In particular, the sorter311can receive this bit stream corresponding to integers410-1to410-8of the set124.

Continuing to block 6.2. At block 6.2, the sorter311can sort the integers410-1to410-8. For example, the sorter311can sort the integers to form a sorted set of integers125. As a specific example, the sorter311can sort the set of integers [14, 1, 23, 15, 19, 59, 5, and 44] as [1, 5, 14, 15, 19, 23, 44, and 59] to generate the sorted set of integers125in order from smallest to largest integer.

Continuing to block 6.3. At block 6.3, the subtractor313can determine a range of the integers410-1to410-8. For example, the subtractor313can identify a lower bound L and an upper bound U for the integers410-1to410-8from the sorted set125. In some examples, the subtractor313can identify the first integer in the sorted set125(e.g., 1, or the like) as the lower bound L and the last integer in the sorted set125(e.g., 59, or the like) as the upper bound U. Additionally, the subtractor313can determine a compressed representation of the upper bound U based on the range. For example, the subtractor313can determine a representation R of the upper bound U based on the following formula, where RUis the representation of the upper bound.
RU=U−(L+n−1)
For example, the subtractor313can determine RUto be 51 (e.g., 59−(1+8−1). Where U is the value of the last integer in the set of integers (59), L is the value of the first integer in the set of integers (1), n is the number of integers in the set (8).

Continuing to block 6.4. At block 6.4, the bit determiner315can determine a number of bits to store the lower bound L and the representation of the upper bound RUin the compressed list information element126. In particular, in some examples, the bit determiner315can determine to store an indication of the lower bound and the upper bound using m bits. In some examples, the bit determiner315can determine to store an indication of the lower bound L using m bits and an indication of the representation RUof the upper bound U using log2[U−(L+n)] bits, or log2[59−(1+6)], which equals 6 bits. For example, given that m equals 6 above, the bit determiner315can determine to store indication of the lower bound as [000001] and the upper bound as [110011] in the compressed list information element126. More specifically, the bit determiner315can store [000001] as the indication of the smallest integer510-1and [110011] as the indication of the largest integer510-2.

Continuing to blocks 6.5 and 6.6, which may be repeated recursively. More particularly, at block 6.5 the subtractor313can recursively sub-divide the range based on a middle integer MXand determine a representation RMXof the middle integer, where x is the number of passes through blocks 6.5 and 6.6, or the number of times the range has been divided. In some examples, x equals n minus 2, or in this example 6. At block 6.6, the bit determiner315can determine the number of bits to use to store the representation RMXin the compressed list information element126.

In general, at block 6.5, the subtractor313can subdivide the range into one or more sub-ranges. More specifically, the subtractor313may identify an integer in the middle position of the range to form sub-ranges defined by the identified middle integer and the range being subdivided. For example, the subtractor313can identify middle integer x from position P based on the following formula, where LXand UXare the upper and lower bounds of the range being subdivided.

P=PL⁢⁢X+PU⁢⁢X2
It is important to note, as the technique recursively subdivides the ranges, the upper and lower bounds of the range (e.g., LXand UX) may change. More specifically, a number of sub-ranges may be formed by the middle integer and the subdivided range. As such, the position P of the upper and lower bounds (e.g., PLXand PUX) may change accordingly. This is explained in greater detail below.

With some examples, at block 6.5, the subtractor313determines a representation RMXof the middle integer based on the following formula.
RMx=Mx−LX−NX+2,
where
NX=PUx−PLx+1

With some examples, at block 6.6, the bit determiner315determines a number of bits to use to store an indication of the representation RMXof the middle integer based on the following formula.
log2[UX−(LX+NX+2)]

Continuing with the example set of integers discussed above, the range of integers represented by the list information element124can be sub-divided 6 times. More specifically, middle integers M1to M6can be recursively identified by continually subdividing the range. Additionally, a representation of these middle integers based on the corresponding upper and lower bounds of the range being subdivided can be determined and stored in the compressed list information element126. In some examples, blocks 6.5 and 6.6 can be repeated recursively in a depth first search method.

In this example, at a first pass through block 6.5, the subtractor313may determine a first middle integer M1, or the integer at position

P=PL+PU2=1+82=5.
In particular, the subtractor313can identify the integer in the sorted set in position5. As such, M1can be identified as the integer 19. Additionally, the subtractor313can determine a representation RM1of the first middle integer based on the range. For example, the subtractor313can determine RM1=M1−L1−(PU−PL+1)+2=19−1−(8−1+1)+2=12. In particular, the subtractor313can determine the representation RM1equals 12.

At a first pass through block 6.6, the bit determiner315can determine a number of bits to store the representation of the first middle integer RM1in the compressed list information element126. For example, the bit determiner315determine to store an indication of the representation of the middle integer RM1using log2[U1−L1−N1+2]=log2[59−1−9+2]=6. In particular, the bit determiner315can determine to store the representation RM1using 6 bits, or as [001100]. More specifically, the bit determiner can add the indication [001100] as the indication of the first middle integer510-3to the compressed list information element126.

At a second pass through block 6.5, the subtractor313can determine a second middle integer M2. In particular, at block 6.5, the subtractor313can determine a middle integer between the integers in the range being subdivided. For example, the subtractor313may determine a middle integer between the sub-range defined by the lower bound L and the first middle integer M1, or between integers 1 and 19 in the sorted set125. More specifically, the subtractor313can determine the integer at position

P=PL+PM⁢⁢12=1+52=3⁢⁢as⁢⁢M2,
which is the integer 14. Additionally, the subtractor313can determine a representation RM2of the second middle integer based on the range. For example, the subtractor313can determine RM2=M2−L2−(PL−PM1+1)+2=14−1−(5−1+1)+2=10. In particular, the subtractor313can determine the representation RM2equals 10.

At a second pass through block 6.6, the bit determiner315can determine a number of bits to store the representation of the second middle integer RM2in the compressed list information element126. For example, the bit determiner315determine to store an indication of the representation of the middle integer RM2using log2[U2−L2−N2+2]=log2[19−1−6+2]=4. In particular, the bit determiner315can determine to store the representation RM2using 4 bits, or as [1010]. More specifically, the bit determiner can add the indication [1010] as the indication of the second middle integer510-4to the compressed list information element126.

At a third pass through block 6.5, the subtractor313can determine a third middle integer M3. In particular, at block 6.5, the subtractor313can determine a middle integer between the integers in the range being subdivided. For example, the subtractor313can determine a middle integer between the sub-range defined by the lower bound L and the second middle integer M2, or between integers 1 and 14 in the sorted set125. More specifically, the subtractor313can determine the integer at position

P=PL+PM⁢⁢22=1+32=2⁢⁢as⁢⁢M3,
which is the integer 5.

Additionally, the subtractor313can determine a representation RM3of the third middle integer based on the range. For example, the subtractor313can determine RM3=M3−L3−(PL−PM2+1)+2=5−1−(3−1+1)+2=3. In particular, the subtractor313can determine the representation RM3equals 3.

At a third pass through block 6.6, the bit determiner315can determine a number of bits to store the representation of the third middle integer RM3in the compressed list information element126. For example, the bit determiner315determine to store an indication of the representation of the middle integer RM3using log2[U2−L2−N2+2]=log2[14−1−3+2]=4. In particular, the bit determiner315can determine to store the representation RM3using 4 bits, or as [0011]. More specifically, the bit determiner can add the indication [0011] as the indication of the third middle integer510-5to the compressed list information element126.

At a fourth pass through block 6.5, the subtractor313can determine a fourth middle integer M4. In particular, at block 6.5, the subtractor313can determine a middle integer between the integers in the range being subdivided. For example, the subtractor313can determine a middle integer between the sub-range defined by the second middle integer M2and the first middle integer M1, or between integers 14 and 19 in the sorted set125. More specifically, the subtractor313can determine the integer at position

P=PM⁢⁢2+PM⁢⁢12=3+52=4⁢⁢as⁢⁢M4,
which is the integer 15. Additionally, the subtractor313can determine a representation RM4of the fourth middle integer based on the range. For example, the subtractor313can determine RM4=M4−L4−(PM2−PM1+1)+2=15−14−(5−3+1)+2=0. In particular, the subtractor313can determine the representation RM4equals 0.

At a fourth pass through block 6.6, the bit determiner315can determine a number of bits to store the representation of the fourth middle integer RM4in the compressed list information element126. For example, the bit determiner315determine to store an indication of the representation of the middle integer RM4using log2[U4−L4−N4+2]=log2[19−14−3+2]=2. In particular, the bit determiner315can determine to store the representation RM4using 2 bits, or as [00]. More specifically, the bit determiner can add the indication [00] as the indication of the fourth middle integer510-6to the compressed list information element126.

At a fifth pass through block 6.5, the subtractor313can determine a fifth middle integer M5. In particular, at block 6.5, the subtractor313can determine a middle integer between the integers in the range being subdivided. For example, the subtractor313can determine a middle integer between the sub-range defined by the first middle integer M1and the upper bound U, or between integers 19 and 59 in the sorted set125. More specifically, the subtractor313can determine the integer at position

P=PM⁢⁢1+PU2=5+82=6.5~7⁢⁢as⁢⁢M5,
which is the integer 44. Additionally, the subtractor313can determine a representation RM5of the fifth middle integer based on the range. For example, the subtractor313can determine RM5=M5−L5−(PU−PUM1+1)+2=44−19−(8−5+1)+2=23. In particular, the subtractor313can determine the representation RM4equals 23.

At a fifth pass through block 6.6, the bit determiner315can determine a number of bits to store the representation of the fifth middle integer RM5in the compressed list information element126. For example, the bit determiner315determine to store an indication of the representation of the middle integer RM5using log2[U5−L5−N5+2]=log2[59−19−4+2]=6. In particular, the bit determiner315can determine to store the representation RM5using 6 bits, or as [010111]. More specifically, the bit determiner can add the indication [010111] as the indication of the fifth middle integer510-7to the compressed list information element126.

At a sixth pass through block 6.5, the subtractor313can determine a sixth middle integer M6. In particular, at block 6.5, the subtractor313can determine a middle integer between the integers in the range being subdivided. For example, the subtractor313can determine a middle integer between the sub-range defined by the first middle integer M1and the fifth middle integer M5, or between integers 19 and 44 in the sorted set125. More specifically, the subtractor313can determine the integer at position

P=PM⁢⁢1+PM⁢⁢52=5+72=6⁢⁢as⁢⁢M6,
which is the integer 23. Additionally, the subtractor313can determine a representation RM6of the sixth middle integer based on the range. For example, the subtractor313can determine RM6=M6−L6−(PM5−PM1+1)+2=23−19−(7−5+1)+2=3. In particular, the subtractor313can determine the representation RM5equals 3.

At a sixth pass through block 6.6, the bit determiner315can determine a number of bits to store the representation of the sixth middle integer RM6in the compressed list information element126. For example, the bit determiner315determine to store an indication of the representation of the middle integer RM6using log2[U6−L6−N6+2]=log2[44−19−3+2]=5. In particular, the bit determiner315can determine to store the representation RM6using 5 bits, or as [00011]. More specifically, the bit determiner can add the indication [00011] as the indication of the fifth middle integer510-7to the compressed list information element126.

Continuing to block 6.7. At block 6.7, the bit determiner may output the compressed list information element126, including compressed indications of the integers in the list information element124. For example, the bit determiner315can output the compressed list information element126as the bit stream [000001 110011 001100 1010 0011 00 010111 00011]. It is noted, that this bit stream has 39 bits, whereas the bit stream corresponding to the list information element has 48 bits. As such, the compressed list information element126has a compression ratio of approximately 1.23.

FIG. 7illustrates an example of a first logic flow. As shown in this figure, the first logic flow includes a logic flow700. Logic flow700may be representative of some or all of the operations executed by one or more logic, features, or devices described herein, such as the system100, the SSD200, or the circuit300.

In this illustrated example, logic flow700at block710may receive a list information element via an input stream, the list information element to include indications of a plurality of integers. For example, the processing unit110, in executing the control routine122, may receive the list information element124(e.g., via the interface130, or the like).

The logic flow700at block720may determine a range of the plurality of integers. For example, the processing unit110, in executing the control routine122, may determine a range (e.g., lower bound and upper bound [L, U], or the like).

The logic flow700at block730may generate a compressed list information element and add an indication of the range to the compressed list information element. For example, the processing unit110, in executing the control routine122, may generate the compressed list information element126and add an indication of the range to the compressed list information element126. In some examples, the processing unit may add an indication of the lower bound L and an indication of a representation of the upper bound RUto the compressed list information element. In some examples, the processing unit110can add the representation of the upper bound RUto the compressed list information element126using less bits than used to indicate the upper bound in the list information element124.

The logic flow700at block740may recursively determine sub-ranges of the plurality of integers. For example, the processing unit110, in executing the control routine122, may recursively determine sub-ranges based on the range by identifying a middle integer MXof the range.

The logic flow700at block750may add, for each of the sub-ranges, an indication of the sub-ranges to the compressed list information element. For example, the processing unit110, in executing the control routine122, may add an indication of a representation RMXthe middle integer of each range or sub-range to the compressed list information126. In some examples, the processing unit110can add the representation of the middle integer RMXto the compressed list information element126using less bits that used to indicate the middle integer in the list information element124.

FIG. 8illustrates an example of a second logic flow. As shown in this figure, the second logic flow includes a logic flow800. Logic flow800may be representative of some or all of the operations executed by one or more logic, features, or devices described herein, such as the system100, the SSD200, and/or the circuit300. In some examples, the system100, the SSD200, and/or the circuit300may implement the logic flow800to recursively determine sub-ranges of the plurality of integers (e.g., to implement block740of logic flow700, or the like).

In this illustrated example, logic flow800at block810may identify a middle integer of a range of integers to form sub-ranges. For example, the processing unit110, in executing the control routine122, may identify a middle integer x from position

P=PL⁢⁢X+PU⁢⁢X2
in the sorted set of integers (e.g., the sorted set125, or the like), where PLXand PUXare the position of the lower and upper bounds of the range being subdivided, respectively.

The logic flow at decision block820may determine whether any of the sub-ranges can be sub-divided. Said differently, logic flow at decision block820may determine whether any of the sub-ranges include 3 or more integers. For example, the processing unit110, in executing the control routine122, may determine (e.g., using a depth first search methodology, or the like) whether the sub-ranges can be subdivided. For decision block830, the logic flow800may continue to block830or may end. In some examples, the logic flow800may continue from decision block820to block830based on a determination that the sub-ranges can be subdivided. In some examples, the logic flow800may continue from decision block820to end based on a determination that the sub-ranges cannot be subdivided.

The logic flow at block830may identify a middle integer of the sub-range to form additional sub-ranges. For example, the processing unit110, in executing the control routine122, may identify a middle integer x from position

P=PL⁢⁢X+PU⁢⁢X2
in the sorted set of integers (e.g., the sorted set125, or the like), where PLXand PUXare the position of the lower and upper bounds of the sub-range being subdivided, respectively.

FIG. 9illustrates a technique900to generate a set of integers from a compressed representation of the set of integers, according to at least some examples of the present disclosure. The technique900is discussed with reference to the circuit300ofFIG. 3, the list information element124ofFIG. 4, and the compressed list information element126ofFIG. 5. Additionally, the technique900is discussed with reference to the example set of integers [14, 1, 23, 15, 19, 59, 5, and 44] used above and the example compressed bit stream [000001 110011 001100 1010 0011 00 010111 00011] representing the example set of integers. However, it is noted the technique900can be implemented by any of the systems and/or devices discussed herein, such as, for example, the system100, the SSD200, the circuit300, or the like. Furthermore, the technique900can be implemented to generate a set of integers from a compressed representation of the set of integers. Furthermore, binary encoding is used for the indications of integers in this example for purposes of convenience. However, this is not to be limiting and other encoding mechanisms, e.g., hexadecimal, or the like may be implemented. Examples are not limited in these contexts.

The technique900may begin at block 9.1. At block 9.1 the sorter311can receive the list information element124. For example, the sorter311can receive, via the interface130, the compressed list information element126. The compressed list information element126can include an indication of a smallest integer (e.g.,510-1, or the like), and indication of a largest integer (e.g.,510-2, or the like) and indications of middle integers (e.g.,510-3to510-8, or the like) For example, for purposes of discussion only, the compressed list information element126can include indications of n integers, represented as the following bit stream [000001 110011 001100 1010 0011 00 010111 00011], where n equals 8.

Continuing to block 9.2. At block 9.2, the sorter311can determine a smallest and a largest integer in the set of integers. For example, the sorter311can determine a smallest integer L, from the indication of the smallest integer510-1and a largest integer U from the indication of the largest integer510-2from the compressed list information element126. In some examples, the sorter311can identify the smallest integer as the first integer indicated in the compressed list information element126(e.g., 1, or the like) as the smallest integer is indicated in the list explicitly. In some examples, the sorter311can identify the largest integer as the second integer indicated in the compressed list information element126(e.g., 59, or the like) as the largest integer is indicated in the list explicitly. In some examples, the sorter311can identify the largest integer from a representation R of the upper bound U based on the following formula, where RUis the representation of the upper bound.
U=RU+(L+n−1)
For example, the sorter311can determine the largest integer to be 59 from RU(e.g., 51+(1+8−1).

Where RUis the value of the representation of the largest integer in the set of integers (51), L is the value of the first integer in the set of integers (1), n is the number of integers in the set (8).

Continuing to block 9.3, the subtractor313can determine a range based on the smallest integer and the largest integer. For example, the subtractor313can determine a position PLof the smallest integer in the set of integers and a position PUof the largest integer in the set of integers.

Continuing to blocks 9.4 and 9.5, which may be repeated recursively. More particularly, at block 9.4 the bit determiner can recursively determine a number of bits in which a representation RMXof a middle integer MXin the compressed list information element126, where x is the number of passes through blocks 9.4 and 9.5, or the number of times a middle integer has been indicated in the compressed list information element126. At block 9.5, the subtractor313can determine the middle integer MXbased on the representation RMXand the range or sub-range to which the middle integer corresponds.

In general, at block 9.4, the bit determiner315recursively determine a number of bits in which the representation RMXof the middle integer MXis indicated, for example, based on the following formula.
log2[UX−(LX+NX+2)]
The bit determiner313can read out this number of bits to retrieve the middle integer representation RMX. In particular, continuing with the example set of integers discussed above, representations of 6 middle integers are indicated in the compressed list information element126. As such, representations of middle integers RM1to RM6can be recursively identified.

In general, at block 6.5, the subtractor313can determine the middle integer MXfrom the representation RMXand the range. More specifically, the subtractor313may identify a middle integer from the representation RMXof the middle integer, for example, based on the following formula.
Mx=RmX+LX+NX−2,
where
NX=PUx−PLx+

An example of recusivly iterating through block 9.4 and 9.5 are given using the example compressed list information element having the following bit stream [000001 110011 001100 1010 0011 00 010111 00011], corresponding to the following set of integers [1, 5, 14, 15, 19, 23, 44, and 59]. In this example, at a first pass through block 9.4, the bit determiner315may determine that the representation of the first middle integer RM1, or the integer at position

P=PL+PU2=1+82=5
is indicated in the compressed list information element using log2[U1−L1−N1+2]=log2[59−1−8+2]=6 bits. In particular, the bit determiner315can determine that the representation RM1is indicated using 6 bits. Additionally, the bit determiner315can read out the next 6 bits from the compressed list information element126, which is [001100], or 12 in decimal.

At a first pass through block 9.5, the subtractor313can identify the first middle integer M1from the representation of the middle integer RM1. As such, M1can be identified as the integer 19. More specifically, the subtractor313can identify M1from the range and the representation, for example, as follows: M1=RM1+L1+N1−2=12+1+8−2=19. In particular, the subtractor313can determine the middle integer M1equals 19.

At a second pass through block 9.4, the bit determiner315may determine that the representation of the second middle integer RM2, or the integer at position P=PL+PM12=1+52=3 is indicated in the compressed list information element using log2[U2−L2−N2+2]=log2[19−1−5+2]=4 bits. In particular, the bit determiner315can determine that the representation RM2is indicated using 4 bits. Additionally, the bit determiner315can read out the next 4 bits from the compressed list information element126, which is [1010], or 10 in decimal.

At a second pass through block 9.5, the subtractor313can identify the second middle integer M2from the representation of the middle integer RM2. As such, M2can be identified as the integer 14. More specifically, the subtractor313can identify M2from the range and the representation, for example, as follows: M2=RM2+L2+N2−2=10+1+5−2=14. In particular, the subtractor313can determine the middle integer M2equals 14.

At a third pass through block 9.4, the bit determiner315may determine that the representation of the third middle integer RM3, or the integer at position P=PL+PM22=1+32=2 is indicated in the compressed list information element using log2[U3−L3−N3+2]=log2[14−1−3+2]=4 bits. In particular, the bit determiner315can determine that the representation RM3is indicated using 4 bits. Additionally, the bit determiner315can read out the next 4 bits from the compressed list information element126, which is [0011], or 3 in decimal.

At a third pass through block 9.5, the subtractor313can identify the third middle integer M3from the representation of the middle integer RM3. As such, M3can be identified as the integer 5. More specifically, the subtractor313can identify M3from the range and the representation, for example, as follows: M3=RM3+L3+N3−2=3+1+3−2=5. In particular, the subtractor313can determine the middle integer M3equals 5.

At a fourth pass through block 9.4, the bit determiner315may determine that the representation of the fourth middle integer RM4, or the integer at position

P=PM⁢⁢3+PM⁢⁢12=3+52=4
is indicated in the compressed list information element using log2[U4−L4−N4+2]=log2[19−14−3+2]=2 bits. In particular, the bit determiner315can determine that the representation RM4is indicated using 2 bits. Additionally, the bit determiner315can read out the next 2 bits from the compressed list information element126, which is [00], or 0 in decimal.

At a fourth pass through block 9.5, the subtractor313can identify the fourth middle integer M4from the representation of the middle integer RM4. As such, M4can be identified as the integer 15. More specifically, the subtractor313can identify M4from the range and the representation, for example, as follows: M4=RM4+L4+N4−2=0+14+3−2=15. In particular, the subtractor313can determine the middle integer M4equals 15.

At a fifth pass through block 9.4, the bit determiner315may determine that the representation of the fifth middle integer RM5, or the integer at position

P=PM⁢⁢1+PU2=5+82=7
is indicated in the compressed list information element using log2[U5−L5−N5+2]=log2[59−19−4+2]=6 bits. In particular, the bit determiner315can determine that the representation RM5is indicated using 6 bits. Additionally, the bit determiner315can read out the next 6 bits from the compressed list information element126, which is [010111], or 23 in decimal.

At a fifth pass through block 9.5, the subtractor313can identify the fifth middle integer M5from the representation of the middle integer RM5. As such, M5can be identified as the integer 44. More specifically, the subtractor313can identify M5from the range and the representation, for example, as follows: M5=RM5+L5+N5−2=23+19+4−2=44. In particular, the subtractor313can determine the middle integer M5equals 44.

At a sixth pass through block 9.4, the bit determiner315may determine that the representation of the sixth middle integer RM6, or the integer at position P=PM1+PM52=5+72=6 is indicated in the compressed list information element using log2[U5−L5−N5+2]=log2[44−19−3+2]=5 bits. In particular, the bit determiner315can determine that the representation RM6is indicated using 5 bits. Additionally, the bit determiner315can read out the next 5 bits from the compressed list information element126, which is [00011], or 3 in decimal.

At a sixth pass through block 9.5, the subtractor313can identify the sixth middle integer M6from the representation of the middle integer RM6. As such, M6can be identified as the integer 23. More specifically, the subtractor313can identify M6from the range and the representation, for example, as follows: M6=RM6+L6+N6−2=3+19+3−2=23. In particular, the subtractor313can determine the middle integer M6equals 23.

FIG. 10illustrates an example of a first storage medium. As shown in this figure, the first storage medium includes a storage medium1000. The storage medium1000may comprise an article of manufacture. In some examples, storage medium1000may include any non-transitory computer readable medium or machine readable medium, such as an optical, magnetic or semiconductor storage. In some examples, storage medium1000may store various types of computer executable instructions, such as instructions to implement logic flow600. In some examples, storage medium1000may store various types of computer executable instructions, such as instructions to implement logic flow700. In some examples, storage medium1000may store various types of computer executable instructions, such as instructions to implement logic flow800. In some examples, storage medium1000may store various types of computer executable instructions, such as instructions to implement logic flow900. Examples of a computer readable or machine readable storage medium may include any tangible media capable of storing electronic data, including volatile memory or non-volatile memory, removable or non-removable memory, erasable or non-erasable memory, writeable or re-writeable memory, and so forth. Examples of computer executable instructions may include any suitable type of code, such as source code, compiled code, interpreted code, executable code, static code, dynamic code, object-oriented code, visual code, and the like. The examples are not limited in this context.

FIG. 11illustrates an example system1100. In some examples, as shown in this figure, the system1100may include a processing component1110, other components1180, or a communications interface1190. According to some examples, system1100may be implemented in a device to compress a set of integers.

According to some examples, processing component1110may execute processing operations or logic for system100, SSD200, circuit300, and/or storage medium1000. Processing component1110may include various hardware elements, software elements, or a combination of both. Examples of hardware elements may include devices, logic devices, components, processors, microprocessors, circuits, processor circuits, circuit elements (e.g., transistors, resistors, capacitors, inductors, and so forth), integrated circuits, application specific integrated circuits (ASICs), programmable logic devices (PLDs), digital signal processors (DSPs), field programmable gate array (FPGA), memory units, logic gates, registers, semiconductor device, chips, microchips, chip sets, and so forth. Examples of software elements may include software components, programs, applications, computer programs, application programs, device drivers, system programs, software development programs, machine programs, operating system software, middleware, firmware, software modules, routines, subroutines, functions, methods, procedures, software interfaces, application program interfaces (APIs), instruction sets, computing code, computer code, code segments, computer code segments, words, values, symbols, or any combination thereof. Determining whether an example is implemented using hardware elements and/or software elements may vary in accordance with any number of factors, such as desired computational rate, power levels, heat tolerances, processing cycle budget, input data rates, output data rates, memory resources, data bus speeds and other design or performance constraints, as desired for a given example.

In some examples, other components1180may include common computing elements or circuitry, such as one or more processors, multi-core processors, co-processors, memory units, interfaces, oscillators, timing devices, and so forth. Examples of memory units may include without limitation various types of computer readable and machine readable storage media in the form of one or more higher speed memory units, such as read-only memory (ROM), random-access memory (RAM), dynamic RAM (DRAM), Double-Data-Rate DRAM (DDRAM), synchronous DRAM (SDRAM), static RAM (SRAM), programmable ROM (PROM), erasable programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), flash memory or any other type of storage media suitable for storing information.

In some examples, communications interface1190may include logic and/or features to support a communication interface. For these examples, communications interface1190may include one or more communication interfaces that operate according to various communication protocols or standards to communicate over communication links or channels. Communications may occur via use of communication protocols or standards described in one or more industry standards (including progenies and variants) such as those associated with the PCI Express, SATA, SAS (Serial Attached SCSI) standard or specifications.

It should be appreciated that the example power loss shutdown system1100shown in the block diagram of this figure may represent one functionally descriptive example of many potential implementations. Accordingly, division, omission or inclusion of block functions depicted in the accompanying figures does not infer that the hardware components, circuits, software and/or elements for implementing these functions would necessarily be divided, omitted, or included in embodiments.

An apparatus comprising: an interface to receive a set of integers; logic, at least a portion of which is implemented in hardware, the logic to: determine a range of the set of integers based on a largest and a smallest integer of in the set of integers; generate a compressed list information element; add an indication of the range to the compressed list information element; recursively subdivide the range into one or more sub-ranges; and add, for each of the one or more sub-ranges, an indication of the one or more sub-ranges to the compressed list information element.

The apparatus of example 1, comprising a computer-readable storage, the logic to store the compressed list information element to the computer-readable storage.

The apparatus of example 1, the logic to send a control signal to the interface to cause the interface to output the compressed list information element via an output stream.

The apparatus of example 1, the logic to sort the set of integers based at least in part on a value of the integers.

The apparatus of example 4, the logic to: determine the smallest integer of the set of integers; and determine the largest integer of the set of integers.

The apparatus of example 5, the logic to: add an indication of the smallest integer to the compressed list information element; and add an indication of the largest integer to the compressed list information element.

The apparatus of example 6, the logic to add an indication of the largest integer to the compressed list information element based at least in part on RU=U−(L+n−1), where RUis a representation of the largest integer, U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The apparatus of example 6, wherein the indication of the largest integer is added to the compressed list information element using log2[U−(L+n)] bits, where U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The apparatus of example 6, the logic to: determine a first middle integer of the set of integers based at least in part on the range; determine a first sub-range of the set of integers based at least in part on the smallest integer and the first middle integer; and determine a second sub-range of the set of integers based at least in part on the first middle integer and the largest integer.

The apparatus of example 9, the logic to: determine a second middle integer of the set of integers based at least in part on either the first sub-range or the second sub-range; and determine a third sub-range of the set of integers based at least in part on the second middle integer and either the smallest integer or the largest integer.

The apparatus of example 9, the logic to: determine a compressed representation of the first middle integer based at least in part on the smallest integer and the largest integer; add an indication of the compressed representation of the first middle integer to the compressed list information element.

The apparatus of example 11, wherein the compressed representation is based at least in part on RMx=Mx−LX−NX+2, where RMXis the compressed representation, MXis the middle integer, Lx is the smallest integer, and NXis the number of integers in the first sub-range.

The apparatus of example 12, wherein the indication of the compressed representation is added to the compressed list information element using log2[UX−(LX+NX+2)] bits, where UXis the first middle integer, LXis the smallest integer, and NXis the number of integers in the first sub-range.

A computer-implemented method comprising: receiving a set of integers via an input stream; determining a range of the set of integers based at least in part on a smallest and a largest integer of the set of integers; generating a compressed list information element; adding an indication of the range to the compressed list information element; recursively determining one or more sub-ranges of the set of integers; and adding, for each of the one or more sub-ranges, an indication of the one or more sub-ranges to the compressed list information element.

The computer-implemented method of example 14, comprising storing the compressed list information element to a memory storage location.

The computer-implemented method of example 14, comprising outputting the compressed list information element via an output stream.

The computer-implemented method of example 14, comprising sorting the set of integers based at least in part on a value of the integers.

The computer-implemented method of example 17, determining the range of the set of integers comprising: determining the smallest integer of the set of integers; and determining the largest integer of the set of integers.

The computer-implemented method of example 18, adding the indication of the range to the compressed list information element comprising: adding an indication of the smallest integer to the compressed list information element; and adding an indication of the largest integer to the compressed list information element.

The computer-implemented method of example 19, wherein the indication of the largest integer is based at least in part on RU=U−(L+n−1), where RUis a representation of the largest integer, U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The computer-implemented method of example 20, wherein the indication of the largest integer is added to the compressed list information element using log2[U−(L+n)] bits, where U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The computer-implemented method of example 19, recursively determining the one or more sub-ranges of the set of integers comprising: determining a first middle integer of the set of integers based at least in part on the range; determining a first sub-range of the set of integers based at least in part on the smallest integer and the first middle integer; and determining a second sub-range of the set of integers based at least in part on the first middle integer and the largest integer.

The computer-implemented method of example 22, recursively determining one or more sub-ranges of the set of integers comprising: determining a second middle integer of the set of integers based at least in part on either the first sub-range or the second sub-range; and determining a third sub-range of the set of integers based at least in part on the second middle integer and either the smallest integer or the largest integer.

The computer-implemented method of example 22, adding an indication of the one or more sub-ranges to the compressed list information element comprising: determining a compressed representation of the first middle integer based at least in part on the smallest integer and the largest integer; and adding the compressed representation of the first middle integer to the compressed list information element.

The computer-implemented method of example 24, wherein the compressed representation is based at least in part on RMx=Mx−LX−NX+2, where RMXis the compressed representation, MXis the middle integer, LXis the smallest integer, and NXis the number of integers in the first sub-range.

The computer-implemented method of example 25, wherein the indication of the compressed representation is added to the compressed list information element using log2[UX−(LX+NX+2)] bits, where UXis the first middle integer, LXis the smallest integer, and NXis the number of integers in the first sub-range.

At least one machine readable medium comprising a plurality of instructions that in response to be executed by system at a host computing platform cause the system to carry out a method according to any one of examples 14 to 26.

An apparatus comprising means for performing the methods of any one of examples 14 to 26.

At least one machine readable medium comprising a plurality of instructions that in response to being executed on system cause the system to: receive a set of integers via an input stream; determine a range of the set of integers based on a smallest integer and a largest integer of the set of integers; generate a compressed list information element; add an indication of the range to the compressed list information element; recursively determine one or more sub-ranges of the set of integers; and add, for each of the one or more sub-ranges, an indication of the one or more sub-ranges to the compressed list information element.

The at least one machine readable medium of example 29, the instructions to further cause the system store the compressed list information element to a memory storage location.

The at least one machine readable medium of example 29, the instructions to further cause the system output the compressed list information element via an output stream.

The at least one machine readable medium of example 29, the instructions to further cause the system sort the set of integers based at least in part on a value of the integers.

The at least one machine readable medium of example 32, the instructions to further cause the system to: determine the smallest integer of the set of integers; and determine the largest integer of the set of integers.

The at least one machine readable medium of example 33, the instructions to further cause the system to: add an indication of the smallest integer to the compressed list information element; and add an indication of the largest integer to the compressed list information element.

The at least one machine readable medium of example 34, wherein the indication of the largest integer is based at least in part on RU=U−(L+n−1), where RUis a representation of the largest integer, U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The at least one machine readable medium of example 35, wherein the indication of the largest integer is added to the compressed list information element using log2[U−(L+n)] bits, where U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The at least one machine readable medium of example 34, the instructions to further cause the system to: determine a first middle integer of the set of integers based at least in part on the range; determine a first sub-range of the set of integers based at least in part on the smallest integer and the first middle integer; and determine a second sub-range of the set of integers based at least in part on the first middle integer and the largest integer.

The at least one machine readable medium of example 37, the instructions to further cause the system to: determine a second middle integer of the set of integers based at least in part on either the first sub-range or the second sub-range; and determine a third sub-range of the set of integers based at least in part on the second middle integer and either the smallest integer or the largest integer.

The at least one machine readable medium of example 37, the instructions to further cause the system to: determine a compressed representation of the first middle integer based at least in part on the smallest integer and the largest integer; and add the compressed representation of the first middle integer to the compressed list information element.

The at least one machine readable medium of example 39, wherein the compressed representation is based at least in part on RMx=Mx−LX−NX+2, where RMXis the compressed representation, MXis the middle integer, LXis the smallest integer, and NXis the number of integers in the first sub-range.

The at least one machine readable medium of example 40, wherein the indication of the compressed representation is added to the compressed list information element using log2[UX−(LX+NX+2)] bits, where UXis the first middle integer, LX is the smallest integer, and NXis the number of integers in the first sub-range.

A memory device comprising: a memory array; logic, at least a portion of which is implemented in hardware, the logic to: receive a set of integers, where each of the set of integers corresponds to a portion of the memory array; determine a range of the set of integers based on a largest integer and a smallest integer in the set of integers; generate a compressed list information element; add an indication of the range to the compressed list information element; recursively subdivide the range into one or more sub-ranges; and add, for each of the one or more sub-ranges, an indication of the one or more sub-ranges to the compressed list information element.

The memory device of example 42, the wherein the memory array is partitioned into memory blocks and the portions of the memory array correspond to bad memory blocks.

The memory device of example 42, the logic to store the compressed list information element to a portion of the memory array.

The memory device of example 42, the logic to sort the set of integers based at least in part on a value of the integers.

The memory device of example 45, the logic to: determine the smallest integer of the set of integers; and determine the largest integer of the set of integers.

The memory device of example 46, the logic to: add an indication of the smallest integer to the compressed list information element; and add an indication of the largest integer to the compressed list information element.

The memory device of example 47, the logic to add an indication of the largest integer to the compressed list information element based at least in part on RU=U−(L+n−1), where RUis a representation of the largest integer, U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The memory device of example 47, wherein the indication of the largest integer is added to the compressed list information element using log2[U−(L+n)] bits, where U is the largest integer, L is the smallest integer, and n is the number of integers in the range.

The memory device of example 47, the logic to: determine a first middle integer of the set of integers based at least in part on the range; determine a first sub-range of the set of integers based at least in part on the smallest integer and the first middle integer; and determine a second sub-range of the set of integers based at least in part on the first middle integer and the largest integer.

The memory device of example 50, the logic to: determine a second middle integer of the set of integers based at least in part on either the first sub-range or the second sub-range; and determine a third sub-range of the set of integers based at least in part on the second middle integer and either the smallest integer or the largest integer.

The memory device of example 50, the logic to: determine a compressed representation of the first middle integer based at least in part on the smallest integer and the largest integer; add an indication of the compressed representation of the first middle integer to the compressed list information element.

The memory device of example 52, wherein the compressed representation is based at least in part on RMx=Mx−LX−NX+2, where RMXis the compressed representation, MXis the middle integer, LXis the smallest integer, and NXis the number of integers in the first sub-range.

The memory device of example 53, wherein the indication of the compressed representation is added to the compressed list information element using log2[UX−(LX+NX+2)] bits, where UXis the first middle integer, LX is the smallest integer, and NXis the number of integers in the first sub-range.

The memory device of any one of examples 46 to 55, the memory array comprising: dynamic random access memory (DRAM), NAND memory, NOR memory, 3-Dimensional cross-point memory, ferroelectric memory, silicon-oxide-nitride-oxide-silicon (SONOS) memory, polymer memory, ferroelectric polymer memory, ferroelectric transistor random access memory (FeTRAM or FeRAM), nanowire, phase change memory, phase change memory with switch, magnetoresistive random access memory (MRAM), or spin transfer torque (STT) memory.