Patent Description:
In particular, it relates to fast lossless compression of <NUM>-bit integers.

Many scientific experiments measure data and convert the analog signals to <NUM> bit digital data (numbers from <NUM> to <NUM>), which are then stored as <NUM> bit unsigned integers, because this is the smallest data type ≥ <NUM> bit that is supported by most computers. Usually, the measured data is noisy with only occasional signal, and the samples are strongly correlated, so the differences between samples are small.

For example, FlashCam is a digital, high- performance camera for ground-based, imaging atmospheric Cherenkov telescopes. Arrays of such telescopes, like the H. experiment or the future observatory CTA, are used to search for astrophysical sources of very high-energy gamma rays.

Functional key building blocks of the FlashCam design are the photodetector plane, with an area of almost <NUM> square meters, and a high-performance, fully digital trigger and readout system. The photodetector plane consists of <NUM> modules, each containing <NUM> photomultiplier tubes (PMT) with peak quantum efficiencies above <NUM>%. The analogue signals of the PMTs are digitized continuously with a sampling rate of <NUM> million samples per second at <NUM>-bit resolution. The data stream of the digitized signals is processed in real time by <NUM> FPGA-based processors, working in parallel. Using digital filter techniques implemented on the FPGAs it is possible to identify coincidences of faint, nanosecond-long light flashes originating from air showers, and to record sequences of the corresponding images with repetition time of <NUM> nanoseconds. Depending on configuration, such "nano-movies" can be recorded with a duration of up to about <NUM> microseconds. The image data is then transferred into a high-performance server via an Ethernet-based front-end readout. Using an optimized scheme, more than <NUM> GByte/s can be transferred without packet loss, resulting in a dead time-free acquisition of more than <NUM> image sequences per second with a duration of about <NUM> nanoseconds.

The huge data rates of such experiments require compression, not only for saving disk space, but also for increasing I/O speed. Often, signal extraction and noise reduction cannot be done immediately, because the complete data set is needed for the calibration afterwards. Even after calibration, one often desires to keep as much data as possible in order to recalibrate and reanalyze the data, when errors were found in the original algorithms.

While disk space has become cheap, the time for reading and writing the data (I/O) is often the bottleneck.

HDD (Hard Disks Drives) offer I/O speeds of ≈ <NUM> GB/s, and SSD (Solid State Disks) offer ≈ <NUM> GB/s. This is by far not enough to handle the data streams of large experiments. The solution is to install disk arrays, which can achieve aggregate speeds of some GB/s. However, the larger these arrays, the more expensive they are, not to mention the network interfaces. Moreover, since in particular astroparticle physics experiments need to be far away from cities - and thus also far away from power plants, computing centers and fast telecommunication lines - the problem of efficient data handling becomes even more important.

Compression of the data can help improve the I/O speed, because the amount of data read from or written to disk decreases by factor r, which is the compression ratio. However, when optimizing a compression algorithm for a low r, the compression speed vc and the decompression speed vd must not be disregarded. If r × v is not well above the disk I/O speed, there might be no advantage in compression.

It is important that the compression algorithm is lossless, because since it is not always possible to distinguish between signal and noise during data acquisition; it would be too dangerous to use a lossy compression algorithm and perhaps loose important parts of the data.

Most general-purpose lossless compression algorithms, like gzip, achieve good compression ratios and decompression speeds, but with insufficient compression speed. During data acquisition, however, there can be time constraints due to high data rates, so high compression speeds would be very helpful.

For example, the data rate of input stream is <NUM> GB/s, the compression ratio r = <NUM>, the compression speed <NUM> GB/s and the write speed of the disk is <NUM> GB/s. If the compression speed was fast enough, the input stream could be compressed to <NUM> GB/s and the disk could easily store it. However, since the compression speed is only <NUM> GB/s, it is not possible. In addition, when the input stream and the disk are the same, but a different compression algorithm is used, which compresses worse (r = <NUM>:<NUM>), but faster (<NUM> GB/s), the input stream is compressed to <NUM> GB/s, and since the compression speed is above the input data rate, it is possible to store it to disk. Furthermore, if the (de-) compression is done quickly, there is more time for data analysis. Patent <CIT> discloses techniques for compressing variable length data segments into aligned, fixed-length compressed data buffers.

It is therefore an object of the present invention to provide a more efficient method and system for compressing digital data.

According to a first aspect, the invention comprises a computer-implemented method for compressing digital data, according to claim <NUM>.

Further advantageous embodiments are defined in the dependent claims.

Most advantageously, the relative simplicity of the inventive method allows it to be implemented with a high amount of parallelization and / or using AVX2 or similar special-purpose processor instructions.

The various embodiments of the invention described herein present a tradeoff between speed and compression ratio. They do not provide the maximum possible compression, but are very fast, resulting in significantly increased I/O speed. They are based on the assumption that the input data consists of consecutive unsigned <NUM>-bit integers, where the differences of the integers are small. Moreover, even if some of the input values are not subject to this constraint, effective compression is still possible.

<FIG> shows flowchart of a method <NUM> for compressing digital data according to a further embodiment of the invention.

A block <NUM> of unsigned <NUM>-bit integers is read in step <NUM>. In step <NUM>, one or more so-called morphological wavelet transforms, which will be explained in more detail in relation to <FIG>, are applied to the block <NUM>, in order to obtain one or more minima <NUM> and one or more residuals <NUM>. Based on the residuals <NUM>, one or more bit ranges used for encoding the residuals are selected in step <NUM>. An indicator, i.e. a bitmask <NUM> is output, which indicates the selected bit range(s). In step <NUM>, the residuals are then coded based on the one or more selected bit range(s) in order to obtain coded residuals <NUM>. In step <NUM>, the minima <NUM>, which may also have been coded (not shown), the coded residuals <NUM> and the bit mask(s) <NUM> are then combined and output in step <NUM>.

Then, if there are more than <NUM> values left to compress, the method returns (not shown) to the beginning step <NUM>, and otherwise copies the remaining values to the output and returns. Parallelization of this algorithm is possible, because larger blocks can be processed independently.

<FIG> shows a more detailed flowchart of the iterated morphological wavelet transform step <NUM> in <FIG>.

Mathematical morphology is a theory for the analysis of geometric structures. The basic concept is to traverse the structure X with a structuring element B and modify each point according to the desired operation:.

with Bx = {b + x|b ∈ B}. Therefore, the dilation is the union set of all points in X, each extended by the neighborhood defined by B, and the erosion is the set of all points in X for which B, translated to that point, lies completely in X. A dilation inflates the object, closes small holes inside, and bays at the border of the object, whereas an erosion deflates the object and removes small islands outside and land tongues at the border of the object.

This concept can be extended from bitmasks to grayscale images and other signals. Let f be the input signal and b the structuring function that has support B. Dilation and erosion are then defined as: <MAT> <MAT>.

In case of the <NUM>-dimensional <NUM>-bit unsigned integer input stream that has to be compressed, the structuring element is chosen to be only <NUM> pixels wide. If erosion is then used as low-pass filter and the difference of eroded signal and the original signal as high-pass filter, a morphological wavelet transform can be defined as follows: <MAT> <MAT>.

The inverse transformation is <MAT> <MAT>.

The minima are guaranteed to stay in the range of an unsigned short (<NUM>. <NUM>), the differences, however, can exceed that range - they are in the interval [-<NUM>. Extracting and storing the signs of the differences prevents such overflows. In addition, since the input data is noisy, the signs of the differences are mostly random, so there is no negative impact on the compression ratio.

In contrast to other wavelets that usually use the mean as low-pass filter, morphological wavelets do not merge spikes into the subsampled signal, resulting in smaller differences at the next decomposition level and thus, in a better compression ratio.

For example, given an input signal v being a noisy baseline with occasional spikes on top, M (v) the pairwise mean of v, m(v) the pairwise minimum of v, and d(v) the pairwise absolute differences of v.

The residuals to encode when using the mean are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, but when using the minimum the residuals are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. This example shows how the mean carries spikes down to lower wavelet levels, resulting in larger differences overall, whereas the minimum rids itself of the spikes early, resulting in smaller differences. The worst case for this wavelet transform is a high baseline with occasional downward spikes, in which case the maximum of pairwise samples would be the better low-pass filter in the wavelet decomposition. However, in most data sets, the baseline is below the signal, and marking whether the minimum or the maximum was used would consume extra header space.

These calculations can be executed efficiently with AVX2 instructions, using only one cycle for calculating <NUM> differences or <NUM> minima. However, much more time is spent on rearranging and preparing the data inside the registers.

<FIG> shows an example implementation of how <NUM> unsigned shorts are read from memory and transformed using the morphological wavelet just described.

In the compression algorithm, blocks of <NUM> values are transformed to <NUM> minima and <NUM> differences. The differences are usually small, while the minima need to be transformed again, in order to yield <NUM> minima and <NUM> differences. This recursive process could continue until there is only one minimum and <NUM> differences left, however, here it stops at the fourth level, yielding <NUM> differences and <NUM> minima. Further decompositions would not exploit the parallelism offered by AVX2 fully, because the last <NUM> minima at the fourth level would have to be split up to two half-filled AVX2 registers:
<FIG> shows a flowchart of a method for bitmask selection that can be used in step <NUM> of <FIG>.

The residuals produced by the wavelet transform are all in the interval [<NUM>. <NUM>], because the signs are stored separately. Usually, they are very small, so they can be stored using much less than the <NUM> bit the original numbers used. However, using range coding alone for a block of <NUM> residuals (as in the first embodiment), even one single large value forces the other <NUM> values of the block to be encoded with more bits.

In order to deal with such outliers, it is proposed to use a bit mask for distinguishing different ranges and then to store the values with the necessary number of bits. For example, if the two ranges are <NUM> bit and <NUM> bit and <NUM> numbers are <NUM>-bit while <NUM> numbers are <NUM>-bit, there is an overhead of <NUM> bits for the mask plus <NUM> × <NUM> bits plus <NUM> × <NUM> bits for the values. Additional <NUM> bits are lost, because the <NUM> bits of <NUM>-bit values are not aligned to a byte border. This adds up to <NUM> + <NUM> + <NUM> + <NUM> = <NUM> bits compared to the original <NUM> bits. If there were <NUM> × <NUM> bits and <NUM> × <NUM> bits to store, <NUM> × <NUM> bits are lost because of byte alignment. Although it is possible to concatenate the two-bit streams before storing them to memory, such bit handling is expensive and complicated with AVX2.

The problem with a single bit mask is that it provides only for two ranges and it is not clear which ranges to choose. <NUM> bit and <NUM> bit might be good values for some data, but for other data, <NUM> bit and <NUM> bit might be better. In order to be flexible towards different noise levels and outliers, the ranges <NUM>, <NUM>, <NUM> and <NUM> bit are chosen. Marking the required range requires an overhead of <NUM> bits per number, for the four possibilities <NUM>, <NUM>, <NUM> or <NUM> bit.

The four (<NUM>) least significant bits (bits <NUM>-<NUM>) of all <NUM> numbers are always stored. Then, for all numbers that do not fit into the <NUM>-bit range, the next <NUM> bits (bits <NUM> and <NUM>) are stored. Then, for all numbers that do not fit into the <NUM>-bit range, the next <NUM> bits (bits <NUM> and <NUM>) are stored. Finally, for all numbers that do not fit into the <NUM>-bit range, the last <NUM> bits (bits <NUM>-<NUM>) are stored.

Thus, for a block v of <NUM> unsigned shorts, the three bit masks are created as follows: <MAT>.

A small gain in compression ratio can be achieved by exploiting the fact that the bitmasks already exclude some ranges. For example, if the bitmasks indicate that the number needs <NUM> bits to be stored, it cannot be a number from <NUM>. So the range for <NUM> bit numbers can be shifted from <NUM>. <NUM> to <NUM>. The same holds for the <NUM> bit range, which can be shifted from <NUM>. <NUM> to <NUM>. These optimizations are done in the algorithm, but in order to keep the following examples clear, they are not done here.

The three masks are convenient to have for the algorithm, but storing them as they are would not be good, because they are redundant, which is easy to see because since each number is in exactly one of the four ranges, <NUM> bit must suffice to store the number. The following transformation combines the three masks into two masks: <MAT>.

For the following example of a block v of <NUM> unsigned shorts, Bi is the number of bits needed to store vi, b4, b6 and b8 are the bitmasks that define which of the ranges (<NUM>, <NUM>, <NUM>, <NUM>) needs to be used for storing a number, and x and y are the transformed bit masks.

This algorithm is robust to outliers and noisy data, achieves good compression ratio and speeds of <NUM> GB/s per core for typical data. However, after some testing with different data sets, it turned out that the compression ratio was not always as good as expected.

In order to increase the compression ratio even more, a further embodiment of the invention proposes not to hardcode the ranges (<NUM>, <NUM>, <NUM> and <NUM> bit), but to use dynamic ranges instead.

<FIG> shows a flowchart of an alternative method for range / bitmask selection that can be used in step <NUM> of <FIG>.

According to this embodiment, the final encoding chooses from <NUM> different ranges and range combinations the one that results in the best compression ratio, instead of using one fixed <NUM>-bit mask, like in previous method. On the one hand, a bitmask indicating which of the <NUM> encodings was the optimal one consumes additional <NUM> header bits, but on the other hand, the overhead of <NUM> bits that are necessary for the <NUM>-<NUM>-<NUM>-<NUM> bit encoding of the previous method is gone. However, as will be shown now, some of the <NUM> encodings use a bit mask as well, but those bit masks only distinguish between two ranges and thus only consume <NUM> bit per value, so for the whole block of <NUM> values an overhead of only <NUM> bits is lost.

More particularly, the <NUM> unsigned <NUM>-bit values (i.e. <NUM> numbers from <NUM> to <NUM>) need to be stored in a memory and time efficient way. The values are the residuals (difference limits of wavelet decomposition), so they are usually small and noisy, and it is not worth trying to compress them further. Since they are small, one does not need to use <NUM> bits for each value, but can try to compress them with fewer bits. One could simply find the largest of the <NUM> numbers and store all values with the bit range of that number. However, if the number were an outlier, it would be better to store most numbers with a smaller bit range and store the outlier separately with the higher bit range.

When searching for the best bit range or bit range combination, the following aspects must be considered:.

In the present embodiment, the following <NUM> bit ranges and bit range combinations are proposed: <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>/<NUM>, <NUM>, <NUM>/<NUM>, <NUM>, <NUM>/<NUM>, <NUM>, <NUM>/<NUM>, <NUM>, <NUM>/<NUM>, <NUM>/<NUM>, <NUM>. For each block of <NUM> numbers, <NUM> bits must be used to indicate which of the <NUM><NUM>=<NUM> bit range (combinations) was used.

For a block of <NUM> unsigned shorts, it is first checked how many of them need how many bits to encode. Based on the distribution of the required bit ranges, it is decided if all of them are stored as n-bit values or if bitmask encoding is used and some of them are stored as n-bit values and the rest as m-bit values:.

For each block of <NUM> unsigned shorts, the encoding that uses the least number of bits is chosen.

<FIG> shows (in pseudocode) a binary search method for determining an appropriate bit range (combination). The function ,space' in the pseudocode of <FIG> measures the space requirement using a particular coding scheme, e.g. using a <NUM>/<NUM> combination.

A similar scheme may be built for <NUM>-bit, <NUM>-bit or <NUM>-bit data. For example, <NUM>-bit data can be coded using the following bit ranges: <NUM>, <NUM>, <NUM>, <NUM>, <NUM>/<NUM>, <NUM>/<NUM>, <NUM>/<NUM> and <NUM>.

Since there are <NUM> different encodings, <NUM> header bits are needed to tell which encoding was chosen. Being able to choose from more than these <NUM> possibilities would certainly help encoding the numbers even better, but more than <NUM> header bits would be needed, and furthermore, more encodings would require more range tests, which would slow down the algorithm. The above combinations are a compromise between compression ratio and speed, because they cover many noise levels, signal strengths, and still do not require too much checking. Most importantly, they are simple enough to be programmed with AVX2 instructions, which is usually not true for more sophisticated algorithms, especially if they use Huffman trees and bit streams.

The layout of a compressed block of <NUM> × <NUM> values is:.

Since the <NUM><NUM>-bit range specifiers are consecutively stored as a <NUM>-bit number, it is possible to check using one single if-instruction, if the data was incompressible. As can be seen in the list of encodings above, if a block of <NUM> values is not compressible and can only be stored by copying them, its <NUM>-bit header is <NUM>, which is <NUM> in binary. If all <NUM> blocks are stored in that way, the <NUM> bit number has all bits set, which can be checked with if (x = - <NUM>), where x is the <NUM> bit long integer that contains the <NUM><NUM>-bit range specifiers.

Incompressible data usually has all header bits set to one (<NUM>). However, if not correctly aligned to a <NUM>-bit boundary in memory, compressible <NUM>-bit data also has all header bits set to one (<NUM>), which happens if the file with the data to be compressed has an odd number of header bytes. Here are two examples that show the importance of correct alignment for <NUM> bit unsigned integer compression.

In example <NUM>, the data is aligned to <NUM> bit, so the algorithm would be able to store the numbers as at least <NUM>-bit values instead of <NUM>-bit values. In the next example, the numbers are the same, but a header byte is added, which causes the numbers to be unaligned.

In example <NUM>, the data is not aligned to <NUM> bit anymore, so the lower byte becomes the upper byte and thus, the data becomes incompressible for the range encoder.

In such a case, all <NUM> header bits are set to one, signaling that the data is misaligned (or really not compressible). The block of <NUM> values are not re-read, but instead simply be written without compression. Afterwards, however, the next byte from the input stream is simply copied (to the output stream), causing the input stream to be aligned to <NUM> bit. If the data is incompressible, this does not improve anything, but neither does is make anything worse.

<FIG> shows an example of a <NUM>/<NUM> bit encoding of <NUM> values. In the encoded stream, the bitmask is sent first (<NUM> bytes), followed by ten <NUM>-bit values (<NUM> bits → <NUM> bytes), followed by six <NUM>-bit values (<NUM> bit → <NUM> bytes).

Optionally, heuristical checks (not shown) may be carried out during the initial reading step <NUM> to catch long sequences of constants or incompressible data.

<FIG> shows results of a comparison of the inventive method with known compression methods. Here, the method described in connection with <FIG> (in the following referred to as fc16) is compared to state-of-the-art compression programs in the following table:.

From the various compression algorithms the libraries density and TurboPFor offer, the ones mentioned here in the table performed best on the data set of this benchmark.

Some programs allow control over the compression ratio in exchange for compression speed. Usually, this is done over the command line switches -<NUM> (maximum speed) and -<NUM> (maximum compression). The benchmarks were run on a <NUM>-core Intel(R) Xeon(R) CPU E5-<NUM> v4 @ <NUM> with <NUM> GB RAM, <NUM> kB L1-cache per core, <NUM> kB L2-cache per core, and ≈ <NUM> GB/s disk I/O speed. All programs in this benchmark were run with a single thread, without any other demanding programs running on the machine. Since the (de-) compression speeds can be close to or above the disk I/O speed, all benchmarks were done in-memory using the programs supplied by the authors, so the disk I/O does not throttle the algorithm. For gzip and lzma, there is no in-memory benchmark mode, but since their bottleneck is not the I/O, they simply read the test files from disk and write the compressed output to /dev/null, which means that the output is discarded and no time spent on writing anything to disk. Algorithms <NUM>-<NUM> are not part of this benchmark, because they are in all aspects inferior to algorithm <NUM> (fc16). There are many other compressors, but the above list covers everything from best compression ratio to fastest compression. Comparing to lzma, gzip, zstd, snappy and density is unfair, because those are general-purpose compressors, which means that they can compress any type of data, not just integers, like TurboPFor and fc16. However, since many scientists use them on their data, it might be interesting for them to know how the compression ratio and speed would change, if they used TurboPFor or fc16. Since the compression suites TurboPFor and density provide several compressors, the best three are included in this benchmark.

The test data set comprises the following files (ordered from low noise levels to high noise levels): hawc. dat (HAWC data), gerda. dat (GERDA data), ctamc. dat (CTA prod3 Monte Carlo simulations), fc_300MHz. dat (FlashCam artificially triggered data with a photon rate of <NUM>/pixel), fc_1200MHz. dat (FlashCam artificially triggered data with a photon rate of <NUM>/pixel), chec. dat (CHEC-S data, not aligned to <NUM> bit) and chec_aligned. dat (the same as chec. dat, but with the first byte of the file removed, so the data is aligned to <NUM> bit).

As can be seen in <FIG>, fc16 compresses almost as good as the strongest compression algorithm (lzma), but <NUM> orders of magnitude faster. The closest competitor in compression speed (vbzenc16) has a much worse compression ratio and decompresses significantly slower. Also, its compression speed drops down to half the compression speed of fc16, when the data is not that simple to compress (CHEC and ctamc). The closest competitors in decompression speed and compression ratio (p4nzenc16 and p4nzenc128v16) compress <NUM>% slower than fc16. They have a slightly better compression ratio than fc16, but decompress slower in almost all cases. Furthermore, they cannot handle unaligned data.

When compared to the other fast integer compression algorithms p4nzenc16 and p4nzenc128v16, and is almost always the fastest compressor and decompressor. The general-purpose compressors snappy, chameleon, cheetah, lion and lz4 lose against fc16, because they are slower and their compression ratio is worse. The other general-purpose compressors lzma, gzip and zstd rival fc16 in compression ratio, but are orders of magnitude slower.

The two top plots in <FIG> show the average ratio of (de)compression speed and compression ratio for all data sets. These numbers are important, because they tell the user how much uncompressed data can be processed ("written and compressed" or "read and decompressed"). The bottom plot combines compression speed, decompression speed and compression ratio. It shows the mean of compression and decompression speed, divided by compression ratio, which is the average speed in which uncompressed data can be processed.

Since p4nzenc16 and p4nzenc128v16 have the same compression ratio and compression speed, they have been merged. The same has been done for gzip-<NUM>, gzip-<NUM> and zstd-<NUM>.

The inventive method can be parallelized very easily because a block that is processed independently is only <NUM> bytes in size. Such a small block size also simplifies the implementation in hardware.

The parallelizability is also reflected in the implementation of fc16. It uses multiple threads, whereby the input stream is divided into blocks of typically about <NUM> MB and then each block is processed in a separate thread. Per thread, compression speeds of <NUM>-<NUM> GB/s and decompression speeds of <NUM>-<NUM> GB/s are achieved on normal desktop PCs. The speeds increase with the number of threads, but not linearly. In in-memory tests, multiple threads on a Xeon processor achieved compression speeds of over <NUM> GB/s.

The algorithm has been specially designed to run quickly on CPUs with vector instructions. For the implementation with AVX2, a block size of <NUM><NUM>-bit numbers was used, because AVX2 registers are <NUM> bit large.

The parallelization on this smallest level then works by applying one arithmetic operation to all <NUM> numbers simultaneously. For example: <NUM> numbers x[<NUM>], x[<NUM>],. , x[<NUM>] in an AVX2 register from which one wants to subtract one number n: AVX2 works in principle like this: y = vector_subtract(x, n), costing one processor clock cycle. Using serial programming, one would have to use a loop: for (i = <NUM>; i < <NUM>; i++) {y[i] = x[i] - n;}, costing a lot more clock cycles. The inventive fc16-algorithm is kept extra simple, so that it is almost only made up of such simple operations as addition, subtraction, comparison etc., which exist as vector instructions and which usually only need one clock cycle.

When designing an algorithm that should be parallelizable with AVX2, one is extremely limited because fewer arithmetic operations are at one's disposal and (even more important) because all numbers in a register are treated equally.

In conclusion, the reasons for the suitability of the inventive method for parallelization are:.

The algorithm is more energy-efficient than conventional algorithms that first have to construct a Huffman tree or similar.

Since the algorithm is also suitable for image compression, there are many possible applications. For example, during test drives of self-propelled cars, all sensor data (over <NUM>% are <NUM> bit RGB raw streams as in the benchmark above) are recorded, so that later it can be understood why the system reacted in what way. Per day and car <NUM>-<NUM> TB of data are stored on such a test drive. All data are recorded without loss and data storage is a limiting factor. There are companies that have specialized in selling such recording boxes to car manufacturers. With the inventive method, the data acquisition rate or data capacity can be doubled.

As a further example, when professional photographers take serial pictures with their SLR cameras with e.g. <NUM> megapixels and <NUM> fps in RAW format, the SD card does not follow the writing and the pictures have to be stored in a cache. This is why the maximum continuous shooting rate or the duration in which pictures are taken in series is limited. Also, the SD card is quickly full. Using the inventive method (in the FPGA or chip) in the camera, one could take more than twice as long continuous shooting and store twice as many images on the SD card.

In a further example, when large videos are edited in video editors, the videos often have to be written to the hard disk in between and then read again. This is done in raw format, because compression would take too long. Using the inventive method, one could accelerate the I/O. One second of a <NUM> movie with <NUM> and <NUM> bit color depth is only <NUM> MB, but soon there will be <NUM> movies with <NUM> and <NUM> bit color depth, and that's already <NUM> GB/s. With fc16 as a plug-in for the video editors, customers could get faster I/O.

Finally, the inventive method could also be used for compressing a display stream from a graphics card to a monitor.

Claim 1:
Computer-implemented method for fast lossless compression of digital data values, comprising the steps
- obtaining a sequence of digital data values;
- selecting bit lengths of code words, based on the sequence of digital data values, wherein the bit lengths of the code words are non-uniform;
- mapping the sequence of digital data values to a sequence of code words, each code word having one of the selected bit lengths;
- packing the sequence of code words into a sequence of storage words having uniform bit length and corresponding to a fixed-size piece of data handled as a unit by the instruction set or the hardware of a processor;
- outputting the sequence of storage words, together with a first bitmask;
characterized in that the method is implemented using special purpose vector
instructions and the fist bitmask indicates the bit length of each code word.