US5734340A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for storing run-intensive information in compact form
Assignee: CDD TECHNOLOGIES LLC
•
Filing: 1996-08-27
•
Granted: 1998-03-31
•
Expires: 2016-08-27
Abstract
Abstract A method for compressing FAT and FAT-like structures, which include runs of primitives and runs intervening codes, includes the steps of receiving a plurality of primitive runs in a memory and generating a plurality of variable-length code sequences where each code sequence is dedicated to a primitive run. Each code sequence indicates of its dedicated run, a primitive-type, a primitive runlength, the presence of an intervening run and, if present, an intervening runlength, and the presence of a jump value pointer. If a jump value pointer is present, the code sequence further indicates the jumplength, which is indicated as a difference (or α) value. The length of each code sequence varies depending on run characteristics such as primitive runlength, intervening runlengths and jumplength.
Inventors
- 👤 Mark Kevin Kennedy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 04:11
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
132 words
A machine-implemented data compression method, comprising the steps of: receiving an input data string in a memory, said input data string including a plurality of primitive runs; and generating within said memory an output data string including a plurality of code sequences, wherein each code sequence includes a header portion and a stream portion, said header portion having a length equal in length to the header portion of each code sequence and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, where each code sequence is dedicated to a primitive run and indicates of its dedicated primitive run a primitive type and a primitive runlength.
Claim 2
Dependent Claim
132 words
A machine-implemented data compression method, comprising the steps of: receiving an input data string in a memory, said input data string including a plurality of primitive runs; and generating within said memory an output data string including a plurality of code sequences, wherein each code sequence includes a header portion and a stream portion, said header portion having a length equal in length to the header portion of each code sequence and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, where each code sequence is dedicated to a primitive run and indicates of its dedicated primitive run a primitive type and a primitive runlength.
Claim 3
Dependent Claim
74 words
The machine implemented method of claim 1, wherein: said step of receiving an input data string includes receiving said input data string having at least one of said primitive runs including a jump value pointer; and said step of generating an output data string includes generating one of said plurality of code sequences dedicated to said at least one of said primitive runs which further indicates a jumplength relating to said jump value pointer.
Claim 4
Dependent Claim
22 words
The machine implemented method of claim 2, wherein said at least one of said primitive runs terminates in said jump value pointer.
Claim 5
Dependent Claim
50 words
The machine-implemented method of claim 1, wherein: said step of receiving an input data string includes receiving said input data string which further includes a plurality of intervening runs; and said step of generating an output data string includes generating said plurality of code sequences to indicate an intervening runlength.
Claim 6
Dependent Claim
49 words
The machine-implemented method of claim 1, wherein: said step of generating an output data string including a plurality of code sequences includes generating, in said header portion; a primitive type indicator and a runlength-included-in-header indicator, and in said stream portion; a primitive runlength descriptor for describing said primitive runlength.
Claim 7
Dependent Claim
83 words
The machine implemented method of claim 1, wherein: said step of receiving an input data string includes receiving a distributed FAT extent list, wherein each of said primitive runs in said plurality of primitive runs is pre-encoded with its respective runlength, and wherein some of said plurality of primitive runs also include a jump value pointer; and said step of generating said output data string includes generating said plurality of code sequences to further indicate a jumplength related to said jump value pointer.
Claim 8
Dependent Claim
133 words
A machine-implemented data compression method, comprising the steps of: receiving, in a memory, a plurality of primitive runs and intervening runs; generating, within said memory, a plurality of code sequences, where each code sequence includes a header portion and a stream portion, said header portion having a length equal in length to the header portion of each code sequence and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, where each code sequence is dedicated to a primitive run and indicates of its dedicated primitive run a primitive type, a primitive runlength, and a jumplength for a jump value pointer, and further indicates an intervening runlength.
Claim 9
Dependent Claim
133 words
A machine-implemented data compression method, comprising the steps of: receiving, in a memory, a plurality of primitive runs and intervening runs; generating, within said memory, a plurality of code sequences, where each code sequence includes a header portion and a stream portion, said header portion having a length equal in length to the header portion of each code sequence and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, where each code sequence is dedicated to a primitive run and indicates of its dedicated primitive run a primitive type, a primitive runlength, and a jumplength for a jump value pointer, and further indicates an intervening runlength.
Claim 10
Dependent Claim
26 words
The machine-implemented method of claim 7, wherein said primitive runlength, said intervening runlength, and said jumplength are each encoded in said code sequence as delta values.
Claim 11
Dependent Claim
48 words
The machine-implemented method of claim 7, wherein said step of generating a plurality of code sequences includes generating a code sequence wherein said intervening runlength is zero, indicating the absence of an intervening run, and wherein said jumplength is zero, indicating the absence of a jump value pointer.
Claim 12
Dependent Claim
70 words
The machine-implemented method of claim 7, wherein said step of generating a plurality of code sequences includes generating, in said header portion, a primitive type indicator, an intervening run indicators a jump value pointer indicator, and a runlength-included-in-header indicator, and in said stream portion, an intervening runlength descriptor for describing said zero runlength, a primitive runlength descriptor for describing said primitive runlength, and a jumplength descriptor for describing said jumplength.
Claim 13
Dependent Claim
79 words
The machine-implemented method of claim 7, wherein the step of generating a plurality of code sequences includes the steps of: generating one code sequence dedicated to a primitive run having a jump value pointer and wherein said jump value pointer indicates a jump from a current location to a destination location; calculating the jumplength for the jump value pointer by calculating the difference between the destination location and the current location; encoding the jumplength in said one code sequence.
Claim 14
Dependent Claim
41 words
The machine-implemented method of claim 11, wherein said step of encoding said jumplength in said one code sequence includes: encoding said jumplength in a jump descriptor in said stream portion; and encoding a jump descriptor byte-length indicator in said jump descriptor.
Claim 15
Dependent Claim
41 words
The machine-implemented method of claim 7, wherein the step of generating a plurality of code sequences further includes, for each primitive run, the steps determining said primitive runlength; encoding said primitive runlength in the code sequence dedicated to the primitive run.
Claim 16
Dependent Claim
45 words
The machine-implemented method of claim 13, wherein the step of encoding said primitive runlength further includes the steps of: determining that said primitive runlength is at most a maximum-header-runlength; encoding said primitive runlength in said header portion; encoding a runlength-included indicator in said header portion.
Claim 17
Dependent Claim
60 words
The machine-implemented method of claim 13, wherein the step of encoding said primitive runlength further includes the steps of: determining that said primitive runlength is greater than a maximum-header-primitive runlength; encoding said primitive runlength in a primitive runlength descriptor in said stream portion; encoding a runlength-included indicator in said header portion; encoding a primitive-runlength-descriptor byte-length indicator in said header portion.
Claim 18
Dependent Claim
66 words
The machine-implemented method of claim 7, wherein the step of generating a plurality of code sequences further includes, for each primitive run, the steps of: determining said intervening runlength for an intervening run; encoding said intervening runlength in an intervening length descriptor in said stream portion; encoding an intervening-length-descriptor byte-length indicator in said intervening length descriptor; and encoding an intervening run indicator in said header portion.
Claim 19
Dependent Claim
32 words
The machine-implemented method of claim 7, wherein said step of receiving a plurality of intervening runs and primitive runs includes receiving the low 28 bits of the entries in a 32-bit FAT.
Claim 20
Dependent Claim
99 words
The machine-implemented method of claim 16, further comprising the steps of: receiving the upper four bits of the entries in a 32-bit FAT, which include a second plurality of primitive runs; generating within memory a second plurality of code sequences, where each code sequence in said second plurality of code sequences varies in length with respect to other code sequences in said second plurality of code sequences, where each code sequence in said second plurality of code sequences is dedicated to a primitive run in said second plurality of runs and indicates a primitive type and a primitive runlength.
Claim 21
Dependent Claim
32 words
The machine-implemented method of claim 18, wherein the step of generating a second plurality of code sequences includes generating for each code sequence a second header portion and a second stream portion.
Claim 22
Dependent Claim
57 words
The machine-implemented method of claim 18, wherein: said step of receiving the upper four bits of the entries in a 32-bit FAT includes receiving a second plurality runs, including runs of a first primitive and runs of a second primitive, wherein said first primitive is a null-indicator and wherein said second primitive is a multi-bit bit pattern.
Claim 23
Dependent Claim
160 words
A computer readable medium having a set of instructions stored therein, which when executed by a processing unit of a computer, causes the computer to perform the steps of: receiving an input data string in a memory, said input data string comprised of a plurality of primitive runs; and generating within said memory an output data string comprised of a plurality of code sequences, wherein each code sequence includes a header portion and a stream portion, said header portion having a length equal to the length of the header portion of each code sequence in said plurality of codes sequences and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, where each code sequence is dedicated to a primitive run and indicates of its dedicated run a primitive type and a primitive runlength.
Claim 24
Dependent Claim
160 words
A computer readable medium having a set of instructions stored therein, which when executed by a processing unit of a computer, causes the computer to perform the steps of: receiving an input data string in a memory, said input data string comprised of a plurality of primitive runs; and generating within said memory an output data string comprised of a plurality of code sequences, wherein each code sequence includes a header portion and a stream portion, said header portion having a length equal to the length of the header portion of each code sequence in said plurality of codes sequences and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, where each code sequence is dedicated to a primitive run and indicates of its dedicated run a primitive type and a primitive runlength.
Claim 25
Dependent Claim
86 words
The computer readable medium of claim 21, wherein: the instructions for performing the step of receiving an input data string include instructions of receiving said input data string having at least one of said primitive runs including a jump value pointer; and the instructions for performing the step of generating an output data string include instructions for generating one of said plurality of code sequences dedicated to said at least one of said primitive runs which further indicates a jumplength relating to said jump value pointer.
Claim 26
Dependent Claim
22 words
The computer readable medium of claim 22, wherein said at least one of said primitive runs terminates in said jump value pointer.
Claim 27
Dependent Claim
63 words
The computer readable medium of claim 21, wherein: the instructions for performing the step of receiving an input data string include instructions for receiving said input data string which further includes a plurality of intervening runs; and the instructions for performing the step of generating an output data string includes instructions for generating said plurality of code sequences to indicate an intervening runlength.
Claim 28
Dependent Claim
56 words
The computer readable medium of claim 21, wherein the instructions for performing said step of generating an output data string including a plurality of code sequences includes instructions for generating, in said header portion, a primitive type indicator, and a runlength-included-in-header indicator, and in said stream portion, a primitive runlength descriptor for describing said primitive runlength.
Claim 29
Dependent Claim
157 words
A data processing system, comprising: input means for storing a plurality of primitive runs and intervening runs; output means for storing a plurality of code sequences; code sequence generating means, operatively coupled to said input means and said output means, for generating said plurality of code sequences, where each code sequence has a header portion and a stream portion, said header portion having a length equal to the length of the header portion of each code sequence in said plurality of codes sequences and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, and where each code sequence is dedicated to a primitive run and indicates of its dedicated primitive run a primitive-type, a primitive runlength, and a jumplength for a jump value pointer, and further indicates an intervening runlength.
Claim 30
Dependent Claim
157 words
A data processing system, comprising: input means for storing a plurality of primitive runs and intervening runs; output means for storing a plurality of code sequences; code sequence generating means, operatively coupled to said input means and said output means, for generating said plurality of code sequences, where each code sequence has a header portion and a stream portion, said header portion having a length equal to the length of the header portion of each code sequence in said plurality of codes sequences and said stream portion having a length which varies in length with respect to the length of the stream portion of other code sequences in said plurality of code sequences, said stream portion having a length ≧0, and where each code sequence is dedicated to a primitive run and indicates of its dedicated primitive run a primitive-type, a primitive runlength, and a jumplength for a jump value pointer, and further indicates an intervening runlength.
Claim 31
Dependent Claim
40 words
The data processing system of claim 26 wherein: said code sequence generating means includes a processing unit; and memory means operatively coupled to said processing unit, wherein said input means and said output means are included in said memory means.
Claim 32
Dependent Claim
44 words
The data processing system of claim 27 wherein: said code sequence generating means further includes program instructions stored in said memory means, wherein said program instructions direct the processing unit to read said plurality of primitive runs and generate said plurality of code sequences.
Claim 33
Dependent Claim
66 words
The data processing system of claim 28, wherein said code sequence generating means further generates: in said header portion, a primitive-type indicator, an intervening run indicator, a jump value pointer indicator, and a runlength-included-in-header indicator; and in said stream portion, an intervening runlength descriptor for describing said intervening runlength, a primitive runlength descriptor for describing said primitive runlength, and a jumplength descriptor for describing said jumplength.
Claim 34
Dependent Claim
34 words
The data processing system of claim 26, wherein said intervening runlength is zero, indicating the absence of an intervening run, and wherein said jumplength is zero, indicating the absence of a jump value pointer.
References Cited (Backward Citations)
US4560976A
Cited
US4586027A
Cited
US4872009A
Cited
US4992954A
Cited
US5163148A
Cited
US4988998A
Cited
US5548751A
Cited
US5051745A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-30 | 2001-09-29 | 2002-03-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-30 | 2005-09-29 | 2006-03-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-30 | 2009-09-29 | 2010-03-31 | $7700.00 | Window Closed / Lapsed |