HK1094832A1 - System and method for compressing and decompressing data stored to a portable data storage device - Google Patents

Abstract

This invention provides a portable storage device, which can be connected with personal computers conveniently by USB port, IEEEI 394 hot line port or similar ports, in which, said device includes a compression/de-compression engine capable of compressing and de-compressing data and data in the personal computers and other host platforms are compressed by it then stored in a memory of a portable storage device, the compressed data are fetched by the engine and de-compressed then sent to the computers to be used by users.

Description

Apparatus and method for compressing and decompressing data stored in portable data storage device

The application is a divisional application of Chinese patent application with the application number of 02825073.7, the application date of 5/13/2002 and the invention name consistent with the application. Which is related to the following U.S. patent applications, all of the assignee of the present invention, and incorporated herein by reference.

U.S. patent application serial No. 09/803,173 entitled "portable data storage device directly connectable to a computer through a USB connector"; U.S. patent application, serial No. 09/803,157, entitled "portable data storage device with secure mode in operation"; U.S. patent application, serial No. 09/898,365, entitled "portable device with biometric authentication; and U.S. patent application serial No. 09/898,310 entitled "portable device with biometric authentication.

Technical Field

The present invention relates to the field of storing electronic data. More particularly, the present invention relates to compression and decompression of data stored in portable data storage devices.

Background

Portable storage devices, sometimes referred to as "keychain" storage devices or Thumbdrives^TM(the trademark is of the assignee of the present invention) are small portable data storage devices. These devices have become an indispensable class of electronic computer peripheral devices that are widely used in business, educational, and home computing applications. These devices are smaller than other data storage devices, such as Personal Computers (PCs), Personal Digital Assistants (PDAs), magnetic or Compact Discs (CDs). Indeed, the name "key fob" storage devices indicates that these devices are comparable in size to keys. Portable data storage devices are not typically permanently installed on a particular host platform, such as a personal computer. Rather, they can be conveniently connected to and removed from a computer having a suitable connection port (e.g., a serial bus port such as a USB port or an IEEE1394 ("firewire") port). In this way, these devices allow users to transfer data between different computers; otherwise, these computers would not be able to connect. Since these devices use non-volatile solid-state memory (e.g., flash memory) as the storage medium, they do not require moving parts or mechanical actuators for data access. The absence of actuators makes the portable data storage device more compact than surface storage devices such as magnetic or optical disks. Also, because there are no moving parts, reading from and writing to the memory of these storage devices is faster than reading from and writing to a magnetic or optical disk. Portable data storage devices also have greater storage capacity than magnetic disks. The portable data storage device can hold up to 256 mbytes, while the disk is 1.4 mbytes.

Although storing data in portable storage devices has proven useful, the use of these devices has been limited due to the inability to store larger amounts of data without increasing the size of the devices.

Disclosure of Invention

It is therefore an object of the present invention to provide a system and apparatus to enable a user to store a greater amount of data into a portable data storage device than permitted by the prior art. This would allow manufacturers to increase the total amount of data that can be stored in the memory of these devices without increasing the size of the memory and, thus, the size of these devices. In addition, this has the added benefit of allowing manufacturers to reduce the size of these devices without reducing the total amount of data that can be stored by the devices.

According to a first aspect of the present invention there is provided a unitary portable data storage device having a universal serial bus, USB, connector adapted for use with a storage device, the device being connectable directly to a computer via the connector for receiving data in the form of data packets, the storage device comprising: a flash memory having a first storage capacity; and a data compression engine capable of compressing each data packet stored in the flash memory to generate data in the form of a separately compressed data packet, such that the storage capacity of the flash memory exceeds said first storage capacity.

According to a second aspect of the present invention there is provided a method of compressing data, the method comprising the steps of: a) connecting the portable data storage device directly to a communication port of the host platform via a universal serial bus connector; b) receiving data from the communication port in the form of a data packet stream; c) executing a data compression engine residing in the portable data storage device; d) compressing the data packets provided by the host to generate separately compressed data packets; and e) storing the compressed data packets in a memory of the portable data storage device.

According to a third aspect of the present invention there is provided a method of decompressing compressed data packets stored in a memory of a portable data storage device, the method comprising the steps of: a) connecting the portable data storage device directly to a communication port of a personal computer through a Universal Serial Bus (USB); b) executing a data compression/decompression engine residing in the portable data storage device; and c) reading the compressed data packets from the memory of the portable data storage device; d) decompressing the data packets to generate respectively decompressed data packets; and e) sending the decompressed data packet to the host platform.

These and other objects are achieved by the present invention; the present invention includes a portable data storage device that can be conveniently connected to a host platform, such as a personal computer, through a USB port, IEEE1394 port, or the like. The device includes a flash memory, a Read Only Memory (ROM), a Random Access Memory (RAM), a USB controller and a microcontroller. In addition, a data compression and decompression engine is included in the portable data storage device to compress/decompress data when storing and reading data into and from the memory.

Portable data storage device (thumb drive)^TM) The connection is made to a host platform, such as a Personal Computer (PC), by inserting a USB connector into a USB port of the PC. The data to be stored in the portable data storage device is sent in the form of data packets from the personal computer to the working buffer of the portable data storage device. The compression engine reads the data from the buffer and compresses each packet. The compressed data packets are stored in flash memory. To read the data, the compression/decompression engine reads the data from the flash memory and decompresses it. The decompression engine places the decompressed data in a working buffer, from which the data is then sent to the host platform.

Typically, the compression/decompression engine is located in read-only memory, but is uploaded to a microcontroller for execution. In another alternative embodiment, the compression/decompression engine is located in an Application Specific Integrated Circuit (ASIC) chip of the portable data storage device.

The user is unaware of the compression/decompression functionality of the portable data storage device. The user stores the data, but is not aware that the data is compressed. In another alternative embodiment, the user may be aware of these functions and be able to enable/disable the compression function at their discretion. Disabling the compression function may speed up data storage.

Drawings

The objects, functions and advantages of the present invention will become apparent from the following detailed description of the preferred embodiments of the invention, which proceeds with reference to the accompanying drawings.

Fig. 1 is a block diagram illustrating the functional blocks and their intuitive structure of one embodiment of a portable storage device according to the present invention.

Fig. 2 is a flow chart illustrating how the host platform communicates commands to the portable storage device.

Fig. 3 is a flow chart illustrating how data is sent, compressed and stored in the memory of the portable storage device.

Fig. 4 is a flow chart illustrating how data stored in the memory of the portable storage device is accessed.

Detailed Description

The invention will now be described in more detail with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete and will fully convey the invention to those skilled in the art. Indeed, the invention encompasses all alternatives, modifications and equivalents of these embodiments, which fall within the scope and spirit of the invention as defined by the appended claims. Furthermore, in the following detailed description of the present invention, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. However, it will be apparent to one of ordinary skill in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.

FIG. 1 is a block diagram illustrating the functional blocks and intuitive structure of one embodiment of a portable storage device and system according to the present invention. Fig. 1 shows a portable storage device 100 (a small handheld device adapted to be held in the hand) connected via a Universal Serial Bus (USB) port connector, IEEE1394 (i.e., firewire) connector or other port connector 140 to a USB port (or similar port) 192 of a host platform 195 (e.g., a personal computer). In a preferred embodiment, the connection is made without interconnection of wires or cables. The host platform 195 is connected to the power supply circuit 150 located inside the portable device. The power circuit 150 draws power from the host platform and powers the various components of the portable device 100.

Still referring to fig. 1, the portable storage device includes a microcontroller 160, flash memory 180, and a compression/decompression engine 190. It will be appreciated that microcontroller 160 may also be a general purpose microprocessor.

In one embodiment, the working buffer 165 is located within the microcontroller. In another alternative embodiment, working buffer 165 is located outside microcontroller 160 (e.g., within random access memory 120). In the preferred embodiment, the working buffer has a capacity of 16 kbytes.

It should be appreciated that the data compression/decompression engine 190 may be implemented using a number of methods, all of which are within the scope of the present invention. In one embodiment, the compression/decompression engine 190 may be implemented by firmware stored in the non-volatile memory 110 within the portable device 100. In another embodiment, the data compression/decompression engine 190 may be implemented by a portion of the microcontroller 160. In yet another embodiment, the compression/decompression engine 190 may be implemented by a processor separate from the microcontroller 160. In other words, the compression/decompression engine 190 does not need to be fixed to a specific portion of the portable device 100 within the scope of the present invention. Instead, where the compression/decompression engine 190 is located may be selected by design, thus providing design flexibility to accommodate different applications in which the present invention may be used.

After the data is transmitted from the host platform 195 to the portable storage device 100, the data compression/decompression engine 190 compresses the data. Data is transmitted in the form of data packets over the USB bus. The data compression/decompression engine 190 reads data from the working buffer 165 (typically one sector at a time) and compresses the data. In a preferred embodiment, the data is compressed to 50% of its original size. Thus a data packet of size 512 bytes will be compressed to 256 bytes. After compression, the data is stored in flash memory 180. The compression/decompression engine 190 also decompresses data stored in the flash memory 180 and transmits the data to the host platform 195.

In this embodiment, the portable device includes a USB device controller 130 for controlling communication between the portable device 100 and a host platform 195, such as a USB compatible personal computer having a USB host controller 197 therein.

Still referring to fig. 1, the portable device 100 also includes a volatile memory 120 and a non-volatile memory 110. In the preferred embodiment, volatile memory 120 is Random Access Memory (RAM), which acts as the working memory for microcontroller 160 when in operation. In this embodiment, the non-volatile memory 110 is a Read Only Memory (ROM) that may be used to store firmware that may perform various functions of the portable storage device 100.

Additionally, in this embodiment, the portable device 100 includes a write protect switch 170 that, when turned on, enables the microcontroller 160 to disable write access to the flash memory 180. It should be noted that, like the compression/decompression engine 190, the write protect switch may be implemented in a number of ways that are well within the scope of the present invention. The write protect switch 170 may be implemented by: such as application software (e.g., firmware stored in a non-volatile memory), as part of microcontroller 160, or as a processing unit separate from microcontroller 160. In an alternative embodiment, the write-protect switch may be a manual switch that is manually operable by a user.

In the presently preferred embodiment as depicted in FIG. 1, the microprocessor 160 controls the various elements of the portable device 100, including the USB device controller 130, the Read Only Memory (ROM)110 and the Random Access Memory (RAM)120 (and the execution of the firmware code stored therein).

Alternatively, the portable device 100 further includes a USB port (not shown) that provides a convenient capability to connect one or more other USB compatible devices to the portable device via USB.

In one embodiment, drivers (not shown), Application Program Interfaces (APIs), and monitoring programs (not shown) reside on the host platform 195 and communicate with the USB host controller 197 to facilitate operation of the portable device 100.

The structure of portable data storage devices is described in two U.S. patent applications: an application serial number 09/898,365 entitled "portable device with biometric authentication", filed on 7/3/2001; another application is serial No. 09/830,173 entitled "Portable data storage device directly connectable to a computer through a USB connector".

The flow chart of fig. 2 describes the operations that occur when a user connects the portable device 100 with the host platform 195 (step 205) and begins storing data to the portable device 100. In step 205, after connecting with the host platform 195, the portable device 100 proceeds to an initialization process. In a presently preferred embodiment, the initialization process involves establishing contact with the host platform 195 and ensuring that the host platform 195 knows that the portable device 100 has been connected thereto. The host platform 195 requests a service from the portable device 100 by sending a request packet to the USB host controller 197. USB host controller 197 sends a request packet to USB connector 140 through USB port 192. The portable device 140 then performs various operations such as reading data from, writing data to, or deleting data from the flash memory 180, accompanied by compression and decompression of the data.

In step 210, host platform 195 may issue a request in the form of a write command to portable storage device 100 to write data to flash memory 180. In step 215, the USB controller 130 receives a write command. Typically, the write command indicates the number of data packets to be subsequently stored.

The flow chart of fig. 3 describes the operations that occur when data is transferred to the portable device for compression and writing into the flash memory 180. Host platform 195 sends the first packet to USB controller 130 (step 303). In one embodiment, each packet corresponds to a sector or 512 bytes of memory according to the USB2.0 standard. In an alternative embodiment, each packet is 64 bytes, in accordance with the USB1.1 standard.

USB controller 130 receives a data packet from host platform 195 (step 305). USB controller 130 sends the data packet to work buffer 165 (step 310). In the preferred embodiment, the working buffer 165 is capable of holding up to 16 kbytes of data. If the working buffer 165 reaches maximum capacity and cannot store more data, the next packet is rejected and the microcontroller 160 sends a Negative Acknowledgement (NAK) signal to the main controller 195 indicating that the rejected packet was not received (steps 312 and 313). The master controller 195 then sends the rejected packet again (step 303). This process of packet rejection and retransmission continues until the working buffer 165 has sufficient capacity to receive the next packet (step 314).

Microcontroller 160 executes compression/decompression engine 190 (step 315). The compression/decompression engine 190 operates on the data packets stored in the working buffer 165 in a "first-in-first-out" scheme whereby the data packets are compressed in the order they are stored in the working buffer 165 so that the data packet first stored in the working buffer 165 will be compressed first and transferred first to the flash memory 180. In the preferred embodiment, the data is compressed to 50% of its original size. In the preferred embodiment, the compression engine 190 operates to compress one sector (512 bytes) of data at a time when operating in accordance with the USB2.0 standard. In an alternative embodiment, the compression engine 190 operates to compress 64 bytes of data at a time when operating in accordance with the USB1.1 standard. The compressed data is stored in flash memory 180 (step 325).

The memory conversion is controlled by the microcontroller 160. In the preferred embodiment, the host platform (and the user) is unaware that the data is being compressed. To the host platform, the data fills the sectors of flash memory 180 as if it were uncompressed (i.e., each sector has 512 bytes of uncompressed data). Thus, the compressed data written to the first sector appears to the host controller as if it filled the entire sector. In practice, data is compressed from 512 bytes to 256 bytes, and half of the sector space required when the data is uncompressed can store the data. Thus, the second packet, after being compressed from 512 bytes to 256 bytes, is also stored in the first sector. The second packet, which is actually stored in the first sector, appears to the host controller as if it was stored in the second sector. Similarly, the first packet stored in the second sector appears to be stored in the third sector, while the second packet stored in the second sector appears to be stored in the fourth sector.

Typically, a 2-bit error detection and 1-bit correction mechanism (2-bit error detection and 1-bit correction mechanisms) is employed.

If additional packets are present, host controller 195 sends the packets to USB controller 130 (steps 335 and 303). The data compression engine 190 continues to compress additional data packets stored in the working buffer 165 (step 320). When there are no packets that need to be compressed, the data compression and storage process ends.

Fig. 4 depicts the steps of reading data from the memory of the portable data storage device and decompressing.

In step 410, the user connects the portable device 100 with the host platform 195. In step 410, after the portable device is connected to the host platform 195, the portable device 100 proceeds to an initialization process as described above. The host platform 195 requests a service from the portable device 100 by sending a request packet to the USB host controller 197. USB host controller 197 sends a request packet to USB connector 140 through USB port 192.

Host platform 195 can issue a request in the form of a read command to portable storage device 100 to read the data requested by the user (step 420). USB controller 130 receives the read command (step 425). The read command specifies the location of the data in the flash memory 180 and the number of data packets to be read. Since the host platform 195 is not aware that the data is compressed, the data requested by the read command is not necessarily located in the sector that the host platform 195 believes the data is located. For example, as described above, the second packet is actually stored in the second portion of the first sector, as if it were stored in the second sector to host platform 195. Similarly, the first packet stored in the second sector appears to be stored in the third sector, while the second packet stored in the second sector appears to be stored in the fourth sector. Thus, a data request from the host platform 195 may indicate that a particular data packet is stored in the second sector, while, in effect, the data is stored in the second portion of the first sector. To address this problem, microcontroller 160 reads the requested data from flash memory 180 in the manner in which the data is stored.

In step 430, microcontroller 160 executes compression/decompression engine 190. The compression/decompression engine 190 reads the requested packet from the flash memory 180 (step 445). The compression/decompression engine 190 decompresses the data (step 447). The decompressed data is sent to the working buffer 165 (step 450). The decompressed data is sent to the USB controller 130 (step 455). In step 460, the data packet is sent to memory (e.g., random access memory) of the host platform 195.

The data compression/decompression engine 190 continues to read data from the flash memory 180 and decompress it until all requested data has been decompressed and sent to the host platform 195.

Alternatively, host platform 195 issues a request to portable device 100 to read a directory of data stored in flash memory 180. The user can then view the directory on host platform 195 to determine which data he wishes to read from flash memory 180.

It will be clear that the above description relates only to preferred embodiments of the invention. Those skilled in the art may devise other arrangements without departing from the spirit and scope of the present invention. The invention is therefore limited only by the appended claims.

Claims (7)

1. A unitary portable data storage device having a universal serial bus USB connector adapted for use with a storage device, the device being connectable directly to a computer via the connector for receiving data in the form of data packets, the storage device comprising:

a flash memory having a first storage capacity; and

a data compression engine for compressing the data to be compressed,

the data compression engine is capable of compressing each data packet stored in the flash memory to generate data in the form of a separately compressed data packet, such that the storage capacity of the flash memory exceeds said first storage capacity.

2. The unitary portable data storage device of claim 1, further comprising a data decompression engine capable of decompressing data stored in the memory of the portable device.

3. The unitary portable data storage device of claim 1, wherein each data packet is compressed to 50% of its original size.

4. The unitary portable data storage device of claim 1, wherein the data compression engine is user-enabled and disabled.

5. A method of compressing data, the method comprising the steps of:

a) connecting the portable data storage device directly to a communication port of the host platform via a universal serial bus connector;

b) receiving data from the communication port in the form of a data packet stream;

c) executing a data compression engine residing in the portable data storage device;

d) compressing the data packets provided by the host to generate separately compressed data packets; and

e) storing the compressed data packets in a memory of the portable data storage device.

6. The method of claim 5, wherein the step of compressing comprises compressing each packet to 50% of its original size.

7. A method of decompressing compressed data packets stored in a memory of a portable data storage device, the method comprising the steps of:

a) connecting the portable data storage device directly to a communication port of a personal computer through a Universal Serial Bus (USB);

b) executing a data compression/decompression engine residing in the portable data storage device; and

c) reading the compressed data packets from the memory of the portable data storage device;

d) decompressing the data packets to generate respectively decompressed data packets; and

e) the decompressed data packet is sent to the host platform.