Circuit for compressing data and a processor employing same

A decompression circuit for decompressing a compressed data structure, the circuit comprising:

• a) an input for accepting a compressed data structure of individual non-zero data values,
• b) a map register for receiving a map identifying the locations of individual non-zero data values within the decompressed structure with bits, wherein bits in the map register are set to zero when an entry in the decompressed structure corresponding to the bit is zero and the bit is set to one when the entry in the decompressed structure corresponding to the bit is non-zero, and
• c) a memory for storing the decompressed data structure, wherein the circuit is configured decompress the compressed data structure by populating the locations of an unpopulated uncompressed data structure which are specified in the map register as being locations of non-zero data with individual inputted non-zero data values from the compressed data structure and by further populating the locations of the unpopulated uncompressed data structure which are specified in the map register as being locations of zero data with zero data to provide an uncompressed and populated data structure;
• and
• wherein the input comprising an arrangement of adders, each adder accepting an input from the bit map memory, and a plurality of comparators, each comparator comparing two integer inputs, the first input of each comparator being an output from a corresponding adder in the arrangement of adders and the second input to each comparator is a sequencing signal.

A processor chip comprising:

• a compression circuit including:
• a) a data memory for storing a data structure comprising individual data values,
• b) a bit map memory for storing a map, the map storing bits representing the locations of individual zero data values and locations of individual nonzero values within the data structure, wherein a bit is set to zero when an entry in the data structure corresponding to the bit is zero and the bit is set to one when the entry in the data structure corresponding to the bit is non-zero, and
• c) a data output, wherein the circuit is configured to retrieve non-zero data from the data structure in the data memory using the map and provide the retrieved data itself as a compressed data structure in combination with data representing the map on the data output, wherein the compression circuit is responsive to an instruction to store a data structure;
• and
• wherein the data output further comprising an arrangement of adders, each adder accepting an input from the bit map memory, and a plurality of comparators, each comparator comparing two integer inputs, the first input of each comparator being an output from a corresponding adder in the arrangement of adders and the second input to each comparator is a sequencing signal.