Implementing mp3 filter for 7-Zip archiver
For a long time my only archiver is the 7-Zip program. I like its compression ratio and speed, so I use it almost everywhere: to compress software distributions, to archive collections of pictures, as well as to store music releases. I download music from online non-commercial labels, where it most often comes in the form of an archive (zip or rar) containing compositions and cover art. After downloading, the archives are clamped by the 7-Zip program and stored in this form on the hard disk. To listen to music, the archives do not need to be unpacked, since modern players can play music directly from them (in particular, I use Foobar2000). And although the total amount of memory occupied by all the archives is still far from the capacity of the hard drive, I began to be occupied with the idea of ​​improving the compression ratio of mp3 files. As one teacher said, a task is an unsatisfied feeling of anxiety; and it was exactly the feeling that I experienced. I did not want to invent my recoder, so it was decided to try to write a filter that removes any redundant information.
By mp3, we will mean MPEG-1/2 / 2.5 Layer 3. Let's see what an mp3 file is.
So, an mp3 file consists of a set of frames, and the frames can be connected with each other, that is, to decode one frame, you may need to look into another. There may be tags in the file, both before and after the audio data. Each frame stores 1152 samples (for stereo mode) and has a duration of 26 ms. The frame size depends on the bit rate and sample rate used, and is calculated using the following formula:
Padding is a special flag in the frame header indicating that the frame is supplemented with one byte.
')
The frame consists of a header, a verification code (optional), information necessary for decoding samples (we will call this information “side info”, since I could not come up with an acceptable Russian translation of this phrase), the actual samples themselves, and no additional data direct relationship to the coded samples:
The header, 32 bits in size, has the following structure:
In practice, some header fields are not used and / or remain the same throughout the mp3 file. For example, MPEG version, layer index, private bit, copy bit, original bit, etc. If the file was created using a constant bit rate (CBR), then the bitrate index field does not change.
The first thought is that it is not necessary to store all the fields of the frame header, but only those that change throughout the file. Remaining fields that do not change can be saved only once. Walking through the headings of all frames, you can collect statistics and identify the fields that are actually used.
Immediately after the title can be located the verification code CRC. It is a 16-bit integer, calculated using the CRC16 algorithm for the last 16 bits of the frame header and for all side info bytes.
The second thought is that since we know how to calculate the verification code, then it can not be stored. Of course, just like that, we don’t have the right to take the CRC out of the frame and throw it out. First you need to make sure that it represents the correct value, because an error could creep into the verification code itself or the bytes by which it is calculated.
I will not dwell on the anatomy of side info. Side info is a fairly complex structure with many fields that vary in each frame. Rotate the same trick with the side info fields, as with the frame header fields will not work.
The side info is followed by audio data compressed by the Huffman code. In fact, this is not quite the case, since Huffman codes alternate with scale factors (scale factors), but for simplicity, we assume that audio data is located after side info and to the end of the frame.
Between frames there can be any other data, if only among these data there were no signature of the frame header (Sync word).
After studying the source code of 7-Zip, I came across the implementation of the BCJ2 filter, designed to improve the compression of executable files (* .exe, * .dll). A distinctive feature of this filter is that it has one input and four outputs. Each encoder has its own encoder. Thus, it turns out that the input file is divided into 4 streams and each stream is compressed by its own separate encoder.
I liked the idea of ​​several outputs and decided to apply it in my filter:
- pack frame header fields in one thread in accordance with the first thought
- side info packaging in the second stream
- and, finally, pack the rest of the information into the third thread: tags and Huffman codes
The first two streams are compressed using the LZMA algorithm with the settings used inside 7-Zip to compress the archive headers, and the third stream is compressed by the algorithm selected by users in the Add to Archive window.
The encoder works like this: all frames of the file are iterated. The frame is divided into three parts: side info is sent to the side info stream, Huffman codes are sent to the main output stream, and header fields are stored in the buffer. If there is a CRC in the frame and it turns out to be true, then it is skipped, otherwise its value is overwritten into the stream of headers so that when unpacking it can be restored.
Sync word (11 bits) of each header is simply thrown away. The values ​​of the fields that did not change during the file are written to the header stream only once, while the changing fields are written sequentially one after the other.
The decoder mirrors the encoder: first, all headers are restored, then the restoration of each frame begins. It is calculated or restored from the first CRC stream, followed by side info and the rest of the frame.
The implementation does not constitute anything particularly complicated and therefore I don’t see the point here. Sources are laid out on githaba . I will only note that the support for such filters (with one input and several outputs) in 7-Zip is not transparent enough and I had to climb inside 7-Zip, not without soap, in particular, into the 7zUpdate.cpp file. Yes, by the way, the source code for the development of the filter was 7-Zip 9.20.
The compiled dll is on the same github . It needs to replace 7z.dll in the folder where you have 7-Zip installed.
Testing was carried out on a sample of 1351 files with a total volume of 16755839778 bytes (15.605 GB), on a computer with Windows XP operating system, Intel Core 2 6700 processor (2.66 GHz) and three gigs of RAM. Each file was individually compressed into the archive and unpacked. First without using a filter, then with a filter. Everywhere compression level Ultra was used.
Filter allowed to save:
- 236199251 bytes (~ 225 MB) of memory on the hard disk
- 908 seconds (~ 15 minutes) on the package
- 407 seconds (~ 8 minutes) unpacking
As you can see, the packing speed increased by 8%, and the unpacking speed by as much as 15%.
The filter improved the compression ratio of mp3 files by 1.5%. You can’t call this result outstanding, but also bad, because the filter works with compressed data.
That's all. Thanks for attention.
Analysis of the conditions of the problem
By mp3, we will mean MPEG-1/2 / 2.5 Layer 3. Let's see what an mp3 file is.
So, an mp3 file consists of a set of frames, and the frames can be connected with each other, that is, to decode one frame, you may need to look into another. There may be tags in the file, both before and after the audio data. Each frame stores 1152 samples (for stereo mode) and has a duration of 26 ms. The frame size depends on the bit rate and sample rate used, and is calculated using the following formula:
Padding is a special flag in the frame header indicating that the frame is supplemented with one byte.
')
The frame consists of a header, a verification code (optional), information necessary for decoding samples (we will call this information “side info”, since I could not come up with an acceptable Russian translation of this phrase), the actual samples themselves, and no additional data direct relationship to the coded samples:
The header, 32 bits in size, has the following structure:
| Title | Field length | Purpose |
|---|---|---|
| Sync word | eleven | Used to search for a title. All 11 bits are set to “1” |
| MPEG version | 2 | |
| Layer index | 2 | |
| Protection bit | one | If not set, then CRC is present in the frame. |
| Bit rate index | four | |
| Sample Rate Index | 2 | |
| Padding bit | one | The same flag signaling that the frame is supplemented with one byte. |
| Private bit | one | Carries any specific information. |
| Channel coding mode | 2 | Can be mono, stereo, joint stereo, dual channel |
| Mode extension | 2 | Used in the joint stereo channel coding mode |
| Copyright bit | one | If this bit is set, it means that copying a file is illegal |
| Original bit | one | If this bit is set, it means that the file is on its original media. |
| Emphasis | 2 | Tells the decoder that additional audio processing is required. |
In practice, some header fields are not used and / or remain the same throughout the mp3 file. For example, MPEG version, layer index, private bit, copy bit, original bit, etc. If the file was created using a constant bit rate (CBR), then the bitrate index field does not change.
The first thought is that it is not necessary to store all the fields of the frame header, but only those that change throughout the file. Remaining fields that do not change can be saved only once. Walking through the headings of all frames, you can collect statistics and identify the fields that are actually used.
Immediately after the title can be located the verification code CRC. It is a 16-bit integer, calculated using the CRC16 algorithm for the last 16 bits of the frame header and for all side info bytes.
The second thought is that since we know how to calculate the verification code, then it can not be stored. Of course, just like that, we don’t have the right to take the CRC out of the frame and throw it out. First you need to make sure that it represents the correct value, because an error could creep into the verification code itself or the bytes by which it is calculated.
I will not dwell on the anatomy of side info. Side info is a fairly complex structure with many fields that vary in each frame. Rotate the same trick with the side info fields, as with the frame header fields will not work.
The side info is followed by audio data compressed by the Huffman code. In fact, this is not quite the case, since Huffman codes alternate with scale factors (scale factors), but for simplicity, we assume that audio data is located after side info and to the end of the frame.
Between frames there can be any other data, if only among these data there were no signature of the frame header (Sync word).
Algorithm
After studying the source code of 7-Zip, I came across the implementation of the BCJ2 filter, designed to improve the compression of executable files (* .exe, * .dll). A distinctive feature of this filter is that it has one input and four outputs. Each encoder has its own encoder. Thus, it turns out that the input file is divided into 4 streams and each stream is compressed by its own separate encoder.
I liked the idea of ​​several outputs and decided to apply it in my filter:
- pack frame header fields in one thread in accordance with the first thought
- side info packaging in the second stream
- and, finally, pack the rest of the information into the third thread: tags and Huffman codes
The first two streams are compressed using the LZMA algorithm with the settings used inside 7-Zip to compress the archive headers, and the third stream is compressed by the algorithm selected by users in the Add to Archive window.
The encoder works like this: all frames of the file are iterated. The frame is divided into three parts: side info is sent to the side info stream, Huffman codes are sent to the main output stream, and header fields are stored in the buffer. If there is a CRC in the frame and it turns out to be true, then it is skipped, otherwise its value is overwritten into the stream of headers so that when unpacking it can be restored.
Sync word (11 bits) of each header is simply thrown away. The values ​​of the fields that did not change during the file are written to the header stream only once, while the changing fields are written sequentially one after the other.
The decoder mirrors the encoder: first, all headers are restored, then the restoration of each frame begins. It is calculated or restored from the first CRC stream, followed by side info and the rest of the frame.
Implementation and practical results
The implementation does not constitute anything particularly complicated and therefore I don’t see the point here. Sources are laid out on githaba . I will only note that the support for such filters (with one input and several outputs) in 7-Zip is not transparent enough and I had to climb inside 7-Zip, not without soap, in particular, into the 7zUpdate.cpp file. Yes, by the way, the source code for the development of the filter was 7-Zip 9.20.
The compiled dll is on the same github . It needs to replace 7z.dll in the folder where you have 7-Zip installed.
Testing was carried out on a sample of 1351 files with a total volume of 16755839778 bytes (15.605 GB), on a computer with Windows XP operating system, Intel Core 2 6700 processor (2.66 GHz) and three gigs of RAM. Each file was individually compressed into the archive and unpacked. First without using a filter, then with a filter. Everywhere compression level Ultra was used.
| Without a filter | With filter | |
|---|---|---|
| Total amount of compressed data | 16300442691 bytes (15.181 GB) | 16064243440 bytes (14.961 GB) |
| Total time spent on packaging | 12181.09 seconds | 11273.47 sec |
| Total time spent unpacking | 3215.44 sec | 2744.76 seconds |
Filter allowed to save:
- 236199251 bytes (~ 225 MB) of memory on the hard disk
- 908 seconds (~ 15 minutes) on the package
- 407 seconds (~ 8 minutes) unpacking
As you can see, the packing speed increased by 8%, and the unpacking speed by as much as 15%.
Conclusion
The filter improved the compression ratio of mp3 files by 1.5%. You can’t call this result outstanding, but also bad, because the filter works with compressed data.
That's all. Thanks for attention.
Source: https://habr.com/ru/post/125336/
All Articles