当前位置：网站首页>[elt.zip] openharmony paper Club - electronic device software update compression

[elt.zip] openharmony paper Club - electronic device software update compression

2022-06-11 03:35:00 【ELT. ZIP】

This article from the ELT.ZIP The team ,ELT<=>Elite( elite ),.ZIP In compressed format ,ELT.ZIP That is to compress the elite .
member ：
- Sophomore at Shanghai University of engineering and Technology
- Sophomores of Hefei Normal University
- Sophomores at Tsinghua University
- Freshman of Chengdu University of Information Engineering
- Freshmen of Heilongjiang University
- Freshman of South China University of Technology
We are from 6 A place to Classmate , We are OpenHarmony Growth plan gnawing paper Club in , And Huawei 、 Soft power 、 Runhe software 、 Rio d information 、 Shenkaihong Wait for the company , Study and Research Operating system technology …

【 Looking back 】

【 This issue focuses on 】

HCompress Shine in a multi tiered storage environment
Uncover the software update compression algorithm of consumer electronic devices
AIMCS How to compress short strings

【 technology DNA】

【 Intelligent scene 】

**********	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************
scene	Autopilot / AR	Voice signals	Streaming video	GPU Rendering	science 、 Cloud computing	Memory reduction	Scientific application	Medical images	database server	Artificial intelligence image	Text transfer	GAN Media compression	Image compression	File synchronization
technology	Point cloud compression	‎ Sparse fast Fourier transform ‎	Lossy video compression	Grid compression	Dynamic selection compression algorithm framework	lossless compression	Hierarchical data compression	Medical image compression	Lossless universal compression	Artificial intelligence image compression	Short string compression	GAN Compressed on-line multi particle distillation	Image compression	File transfer compression
Open source project	Draco / Based on deep learning algorithm /PCL/OctNet	SFFT	AV1 / H.266 code / H.266 decode /VP9	MeshOpt / Draco	Ares	LZ4	HCompress	DICOM	Brotli	RAISR	AIMCS	OMGD	OpenJPEG	rsync

introduction

Real scene

Many consumer products are popular in the market , Among them, there are consumer electronic products similar to Internet of things devices . With the rapid increase in the number and types of consumer electronic devices , All kinds of software are also becoming popular , For example, our common wechat 、 Tiktok . On our cell phones , It often happens that the mobile phone system needs to be updated or a software needs to be updated , These updates are achieved by connecting to the Internet . however The bandwidth of the Internet is limited , Moreover, users also have certain requirements for the update time , So how to quickly transmit data and apply updates is a problem .

chart 1 Mobile system update
Insert picture description here (a) IPhone to update

(b) Software update of mobile phone

With ECU The complexity and scale of software increase , In the vehicle Electrical control unit (ECU) Mistakes in are also increasing . Networked vehicles need ECU Upgrade of software or security functions . therefore , After the car comes out, it needs to be equipped with wireless communication （Over the Air, OTA） reprogramming ECU Software functions of . Because in the process of software update, you may not be able to drive the car, and the bandwidth of car networking is very limited ,OTA The most important problem of updating is to reduce the update time .

chart 2 vehicle ECU to update

Insert picture description here
(a) adopt OTA Carry out on-board test ECU upgrade
(b) vehicle ECU Overview of software update system

problem

For the update of consumer electronic devices such as mobile phones , Two requirements can be summarized ：
- Reduce code differences between old and new versions , This is based on Differential compression algorithm In terms of the update scheme , Reducing code differences means reducing the amount of data that needs to be transmitted and downloaded .
- Reduce the number of pages written to flash memory , To reduce the time when the equipment is not available . This requires a small amount of data to be downloaded , It is also required to be able to quickly apply the downloaded data to the device , It usually corresponds to the time required for data decompression and flash writing .
For car ECU, There are the following requirements ：
- Reduce software update time , This is the main problem solved by the compression algorithm .
- Ensure the integrity of software updates . in many instances ,ECU Software controls vehicle operation , So for security reasons, integrity is needed .
- Minimize the risk of software updates . Because by OTA Data may be eavesdropped and manipulated during update .
Some other problems will be described in the specific algorithm below .

Related algorithms

Solution based on differential compression algorithm

When making software changes , In many cases, some code will be deleted and added , Pictured 1 Shown . There are also many cases where some code has been changed . however , You can handle this by removing old code and adding new code . therefore , As shown in the figure below , Binary differential update can be implemented with two commands .

Insert picture description here
chart 3 Binary differential

A more specific implementation can be explained by the incremental representation format described below

Incremental representation format

We use the iteration of the following five commands to realize the specific process of incremental representation ：

DATA command
When the contents of the old and new versions are completely different , New data needs to be described . DATA The command itself represents the size of the incoming data , Then there is the data of the specified length .
SKIP command
The content and address location of the new version and the old version are the same, which can be accessed through SKIP Commands together mean . This specifies the size of the part that does not need to be overwritten in flash memory .
COPY command
The old and new versions can only be used in different parts when the code is not in the same position COPY The command says . You can create a new version by moving the location of the data from the old version ; Specify the starting point and size of the data to be copied .
FORCED-FLUSH command
This command specifies to write data to flash memory , And RAM The data corresponding to the increment in is written to the flash memory . After executing this order , We promise there won't be COPY The command attempted to reference memory that has been overwritten with the corresponding older version .
END command
This indicates that the end of the increment has been reached .

Let's intuitively feel the use of the above commands through an example ：
Insert picture description here
chart 4 Examples of differences between old and new software versions

The first piece of code hasn't changed , So we need to use SKIP Command skip , And you need to specify the size of the skipped part , Here for 0x100; The new version adds a new piece of code in the first and second blocks , Because the old version does not exist , So use DATA Command addition , The size is 0x30; Next use COPY The command copies the second piece of code from the old version , Starting from 0x1100, The size is 0x100; Next, use COPY The command copies the third piece of code from the old version , Starting from 0x1250, The size is 0x100. So use the command to indicate that the figure above is ：

SKIP 0x100
DATA 0x30,  Here is the code to be written 
COPY 0x1100, 0x100
COPY 0x1250, 0x100

So update the old version to the new version , With such a piece of code, you can complete the representation of , And The actual increment is mainly caused by SKIP command 、COPY Command and DATA The number of commands determines . If set SKIP,COPY and DATA The times of are s,c and d, The command itself can be expressed in a byte , Location information needs a Bytes , Size information needs n Bytes , and DATA The length of the data can actually be determined by the length of the code written , Suppose the average length of newly added code is l, Then the size occupied by the incremental code is ：
$d s i z e = (a + n + 1) c + (n + 1) s + (l + 1) d$

RSYNC

Let's introduce a commonly used File synchronization algorithm using incremental idea ——rsync. The algorithm is applied to Synchronize two similar files , The main idea is , Find the changed part of the file in some ways , Transmit only differential data , Thus, the data transmission time is greatly reduced .

problem

If we want to synchronize files, we only want to transfer different parts , We need to do... On both sides of the document diff, But these two problems are on two different machines , failure to diff. If we do diff, You have to transfer a file to another machine to do diff, But this way , We passed the whole document , This is contrary to our original intention that we only want to transmit different parts . So we have to think of a way , Keep the documents on both sides out of sight , But you can also know the difference between them .rsync Algorithm The solution is this problem .

Algorithm description

Suppose we have A and B Two computers ,A Access to files X,B Access to files Y,X and Y The contents of the two files are similar .

B Will file Y It is divided into non overlapping sizes in turn S Blocks of bytes , The last piece can be smaller than S;
about Y Every piece of , Calculate two checksums ：32 Bit weak “ rolling ” The checksum And 128 Strength of bit MD5 The checksum ;
B Send these checksums to A;
A Search for X File to find a file with a length of S The block （ Any offset ）, These blocks are related to Y There is also a corresponding weak checksum 、 Strong check , The specific process can be in rsync Core algorithm Found in ;
A towards B Send build X Instructions , Instructions may be to files Y Block reference , It may also be some text data . For and only Y Any block of does not match X Partially send text data .

The end result is to get X Copy of , but Y I can't find it in China. X fragment （ A small amount of data with checksum and block index ） Send via link , The algorithm only needs one round trip .

BPE Algorithm and its improvement

BPE（Byte Pair Encoding, Byte pair encoding ） Is a dictionary based data compression algorithm , It can be combined with differential compression for data compression and decompression of software update .

chart 5 Use BPE Update software in consumer devices
As shown in the figure above , First, the binary differential data is obtained by comparing the old and new versions of the code , And then through OTA And other wireless methods to the target device . In the device , Unzip the old version first （ The old version of the code is stored in flash memory , Unzip from flash memory to... When needed RAM）, This process is very fast , Then the binary differential data is applied to the old version of the code to obtain the new version of the code , Finally, compress the new version of the code , Store to flash memory , It's a very slow process , And by BPE The implementation process of the algorithm determines .
BPE The process of is realized through iteration ： Find the most frequently occurring byte pair in the current text , Then replace it with a byte , The requirement is that this byte does not exist in the previous text , Apply this substitution to the entire text , Then repeat .BPE The output of the algorithm is the compressed data and the dictionary used for extraction . Here's an example of this process ：

Source text	Replace	Replaced text
ABABCDABCDEFABCEFFG	AB->X	XXCDXCDEFXCEFFG
XXCDXCDEFXCEFFG	XC->Y	XYDYDEFYEFFG
XYDYDEFYEFFG	YD->Z	XZZEFYEFFG

The result of compression is “XZZEFYEFFG” And the corresponding Dictionary {“Z”: “YD”, “Y”: “XC”, “X”: “AB”}

As mentioned earlier, it will take a lot of time to compress the new version of code , So there is an improved algorithm , The idea is very clever ：
adopt BPE In the process of the algorithm, we can see that finding the byte pair that appears most frequently when building the dictionary is the reason for the large time complexity of the algorithm , If this process is omitted , Just compress quickly . therefore , When we send binary differential data to the device, we also send the dictionary of the new version code , In this way, after obtaining the new version code on the device, you can use this dictionary to quickly compress . and , This dictionary can be obtained by compressing the new version of code at the development end . The following figure shows the improved code ：

chart 6 Use improved BPE Update software in consumer devices

Solution based on dictionary compression algorithm

above BEP Is an example of a solution based on dictionary compression , But for cars ECU Software update for , There are other issues to consider . mobile phone 、 Tablet and other consumer electronic devices RAM The space is generally large , But ordinary ECU There's not enough RAM, In some cases RAM The size of is smaller than the size of the flash erase block , It is difficult to apply the difference technique to this kind of ECU.
Based on difference / Incremental compression scheme , Although the differential data sent is small , But if you need to read the old version of the code from flash memory to RAM The new version code is obtained by applying the difference data in , This process requires RAM There is enough space to store data of flash erase block size , therefore , about RAM The size is smaller than that of the flash erase block ECU, Differential data / Increment cannot be applied to older versions of code , You can't update .

chart 7 RAM And the size of the number of erasures
RAM The size of is smaller than the size of the erase block in two cases ,1）RAM Too small ,2） Erase block is too large , For the first 2 In this case , Compression technology can be applied , Because the compressed data can be in RAM Upper deployment . Next, we need several compression algorithms for smaller workspace .

Comparison of several compression algorithms

Insert picture description here Table 1 Comparison of typical compression algorithms

Table 1 shows the typical types of four compression algorithms . In this table , We from Compression ratio 、 Required working memory and Expand （ decompression ） Speed The algorithms are compared in three aspects .Bzip2 It is a famous general good compression algorithm , be used for bsdiff.Deflate and LZMA2 It is famous for its good compression ratio and expansion speed .BPE It is one of the fastest expanding algorithms . These are some typical algorithms , There are many similar algorithms .

bzip2 By block sorting and Huffman Code composition , It has a better compression ratio , But it requires a lot of working memory , Not in line with our purpose ;
Deflate from LZ77 and Huffman Code composition , Its compression ratio bzip2 Bad , But the working memory and expansion speed are very good ;
LZMA2 be based on LZ77 And interval coding , It takes time to code ;
We try to evaluate whether they can be used for ECU. These algorithms are used to compress the sample code data , The sample target software is TOPPERS/ASP,ARM Version is 1.9.0. The data before and after each compression algorithm is shown in the table . among ,LZMA2 The compression ratio is the best .Bzip2 and Deflate It can be understood as having the same compression ratio .BPE The compression of is better than others .

Insert picture description here Table two Amount of data before and after compression

chart 8 It shows the compression ratio of each algorithm and the required working memory . As you can see from this picture ,BPE Requires the least amount of working memory . however , Its compression ratio is the worst . From this result, we can see that ,Deflate Apply to have RAM Limited in size ECU.

Insert picture description here chart 8 Working memory size and compression ratio

Deflate Algorithm improvement

Deflate The working memory required by the algorithm decompression process depends on the amount of compressed data , therefore , Pictured 9 The split compression shown may reduce working memory . Compressed data consists of independently compressed split compressed data . The size of each compressed data depends on the size of the working memory . however , Dividing data involves time overhead , therefore , The trade-off between speed and memory should be evaluated .

Insert picture description here
chart 9 Partition data compression

Evaluation of working memory and compression ratio

For split compression , Based on the size of working memory and compression ratio Deflate. chart 10 Sum graph 11 It shows two versions of a software Deflate When decompressing The working memory and Compression ratio situation .

Insert picture description here
chart 10 The working memory size and compression ratio of each compressed data limit ：TOPPERS/ASP, edition 1.7.0

Insert picture description here
chart 11 The working memory size and compression ratio of each compressed data limit ：TOPPERS/ASP, edition 1.9.0

As can be seen from the data in the figure , Compression ratio in the best case （ The larger the compression ratio, the better ） need 480 KB Working memory .

Evaluation of transmission time

Compare the transmission time of compressed data and uncompressed data . use 10 individual ECU Experimentalize , Suppose some of them ECU Cannot update by incremental algorithm . Set the amount of updated data as $U_{size}$ ,CAN The bit rate is $Net_{bitrate}$ , The time required for transmission is T, be ：
$T=\frac{U_{size}}{Net_{bitrate}}$

We assume that TOPPERS/ASP Of 1.7.0 Version update to 1.9.0 edition , also CAN The bit rate is 500 Kbps To assess the . Pictured 12 Shown , The difference between compressed and uncompressed data increases as it cannot be updated incrementally ECU The number increases linearly .

Insert picture description here
chart 12 Comparison of transmission time

In the evaluation environment , All that cannot be updated incrementally and by compression ECU The transmission time is all that can be updated incrementally ECU Five times the transmission time of .

An improved algorithm based on the same dictionary

Insert picture description here chart 13 Software update through compressed data

chart 13 Shows the process of updating the device using general compression technology . The updated code is downloaded and stored in RAM in . After extraction , The data is written to the erased block . under these circumstances , You can update a lot of code by repeating this process for different parts of the whole process .

In the discussion above , We found that LZ77 Of Deflate It is suitable for compressing the updated data , Next, we will discuss based on LZ77 Another algorithm ——Zstandard.

Algorithm

LZ77 Replace the string position and length with the details of the previous occurrence of the same string . If there is no similar string , No replacement . The area of the search string is called the window , It will slide gradually . A dictionary consists of a referenced string .
chart 14 The proposed method is shown , It's primitive LZ77 Improved version . Before leaving the factory , The old version of the code is written to flash memory . The old version is compressed , The dictionary used for extraction is also written on flash memory , And supplied with the old version .

Insert picture description here
chart 14 Conventional methods （ Build a new dictionary ） And improvement methods （ Use an old dictionary ） Data compression

When software updates are needed , Will use Old dictionary New version of compression software , The dictionary is saved with the old version on the attached device . After the compressed data is distributed , Pictured 14 Shown , Compress the old version . The second string “ABC” Replace with the first string in the dictionary “ABC” The position and length of .
The format of extracted and compressed dictionaries should be different , The dictionary used for compression should have indexes, etc . however , In this study , Two dictionaries in different formats are regarded as the same dictionary , Because they just have different formats .
In the figure 14 in , character string “ABC” In the default dictionary （ Old dictionary ） in . then , Reference the string in the new code “ABC” Replace the symbol of with “ABC”. Using this method , The compression ratio is less than that of the conventional method , Pictured 14 The lower part shows . New symbols “D” Added to the old version . There are no symbols in the default dictionary “D”, But the traditional compression method generates a new dictionary , It contains the symbol “D”, Better compression ratio can be obtained .
Compressed data without a dictionary must be downloaded using our proposed method , Compressed data with a new dictionary must be downloaded using conventional methods . This is a trade-off between the two methods . Besides , The proposed method requires additional flash memory . The size of flash memory is also a trade-off between the two methods .

chart 15 Software update process
chart 15 Represents the process of software update from initial shipment to the generation of new software on the target device . We define the shipping version as the old version . Software update means that the old version has been replaced by the new version . Before leaving the factory , The old version passed in the factory based on LZ77 The algorithm is compressed . then , Extract the dictionary part used for extraction from the compressed data . The uncompressed software code and the dictionary used for extraction are written on the flash memory of the factory equipment , This dictionary is used later to extract new data .
During the software update , The new version is compressed in the factory using the old dictionary . Download compression software without Dictionary , On the target device , Use the... On flash memory （ used ） The dictionary starts from RAM Extract new software from . The old code on the erase block is erased ,RAM The new code on is written to the block .

Experiment and evaluation

experiment

The improved algorithm is applied to Toppers In software Advanced Standard Profile kernel , We have prepared four versions , Number from 1.9.0 To 1.9.3. The binary code size of each version is shown in Table 3 .

Insert picture description here Table 3 Data for evaluation

take 1.9.0 As the original version , Measure the compression ratio and multiple update compression ratio of the traditional method and our proposed method .

assessment

Compression ratio

Table 4 shows the compression ratio after compressing each version using conventional methods and improved methods . The default dictionary size is 31304 byte . This dictionary includes all strings and indexes . therefore , Its size is larger than the size of the original data .
Using the proposed method, the compression ratio is very effective ; however , It requires extra flash memory space . It's a trade-off . If the flash memory is too small , The size of the dictionary will be limited . In these cases , Short length strings or strings that are referenced only a few times are omitted to reduce the size of the dictionary . however , The size of the data is larger than the result of the original method .

Insert picture description here

Table 4 Compare the compression ratio

Multiple updates

Software updates to the device may be applied repeatedly . about PC Or mobile software , The new version will be released many times . therefore , We should assume that there will be multiple updates . If binary difference technology is used , No problem , Because the difference between successive versions is usually small . However , Our proposed method uses the initial version of the dictionary . therefore , The difference increases proportionally to the version number . in other words , Updating data becomes more important in proportion to the version number .
Table 4 shows that the increase of compression ratio is linear . However , In some cases , The update time may not be important . chart 16 Shows the relationship between version number and dictionary compression ratio .

Insert picture description here
chart 16 The compression ratio of multiple updates changes