1 //
2 // Copyright (C) 2017 The Android Open Source Project
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 //      http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16 
17 #include "update_engine/payload_generator/deflate_utils.h"
18 
19 #include <unistd.h>
20 
21 #include <algorithm>
22 #include <utility>
23 #include <vector>
24 
25 #include <gtest/gtest.h>
26 
27 #include "update_engine/common/test_utils.h"
28 #include "update_engine/common/utils.h"
29 #include "update_engine/payload_generator/extent_ranges.h"
30 #include "update_engine/payload_generator/extent_utils.h"
31 
32 using puffin::BitExtent;
33 using puffin::ByteExtent;
34 using std::vector;
35 
36 namespace chromeos_update_engine {
37 namespace deflate_utils {
38 
39 // This creates a sudo-random BitExtents from ByteExtents for simpler testing.
40 vector<BitExtent> ByteToBitExtent(const vector<ByteExtent>& byte_extents) {
41   vector<BitExtent> bit_extents;
42   for (auto& byte_extent : byte_extents) {
43     bit_extents.emplace_back(byte_extent.offset * 8 + (byte_extent.offset & 7),
44                              byte_extent.length * 8 - (byte_extent.length & 7));
45   }
46   return bit_extents;
47 }
48 
49 TEST(DeflateUtilsTest, ExtentsShiftTest) {
50   vector<Extent> base_extents = {ExtentForRange(10, 10),
51                                  ExtentForRange(70, 10),
52                                  ExtentForRange(50, 10),
53                                  ExtentForRange(30, 10),
54                                  ExtentForRange(90, 10)};
55   vector<Extent> over_extents = {ExtentForRange(2, 2),
56                                  ExtentForRange(5, 2),
57                                  ExtentForRange(7, 3),
58                                  ExtentForRange(13, 10),
59                                  ExtentForRange(25, 20),
60                                  ExtentForRange(47, 3)};
61   vector<Extent> out_over_extents = {ExtentForRange(12, 2),
62                                      ExtentForRange(15, 2),
63                                      ExtentForRange(17, 3),
64                                      ExtentForRange(73, 7),
65                                      ExtentForRange(50, 3),
66                                      ExtentForRange(55, 5),
67                                      ExtentForRange(30, 10),
68                                      ExtentForRange(90, 5),
69                                      ExtentForRange(97, 3)};
70   EXPECT_TRUE(ShiftExtentsOverExtents(base_extents, &over_extents));
71   EXPECT_EQ(over_extents, out_over_extents);
72 
73   // Failure case
74   base_extents = {ExtentForRange(10, 10)};
75   over_extents = {ExtentForRange(2, 12)};
76   EXPECT_FALSE(ShiftExtentsOverExtents(base_extents, &over_extents));
77 }
78 
79 TEST(DeflateUtilsTest, ShiftBitExtentsOverExtentsTest) {
80   vector<Extent> base_extents = {ExtentForRange(3, 1),
81                                  ExtentForRange(1, 1),
82                                  ExtentForRange(5, 1),
83                                  ExtentForRange(7, 1),
84                                  ExtentForRange(9, 1)};
85   vector<BitExtent> over_extents =
86       ByteToBitExtent({{0, 0}, {100, 2000}, {4096, 0}, {5000, 5000}});
87   vector<BitExtent> out_over_extents =
88       ByteToBitExtent({{12288, 0}, {12388, 2000}, {4096, 0}});
89   ASSERT_TRUE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
90   EXPECT_EQ(over_extents, out_over_extents);
91 }
92 
93 TEST(DeflateUtilsTest, ShiftBitExtentsOverExtentsBoundaryTest) {
94   vector<Extent> base_extents = {ExtentForRange(1, 1)};
95   vector<BitExtent> over_extents = ByteToBitExtent({{2, 4096}});
96   vector<BitExtent> out_over_extents = {};
97   EXPECT_FALSE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
98 
99   base_extents = {ExtentForRange(1, 1)};
100   over_extents = {};
101   out_over_extents = {};
102   EXPECT_TRUE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
103   EXPECT_EQ(over_extents, out_over_extents);
104 
105   base_extents = {};
106   over_extents = {};
107   out_over_extents = {};
108   EXPECT_TRUE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
109   EXPECT_EQ(over_extents, out_over_extents);
110 
111   base_extents = {};
112   over_extents = ByteToBitExtent({{0, 1}});
113   out_over_extents = ByteToBitExtent({{0, 1}});
114   EXPECT_FALSE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
115   EXPECT_EQ(over_extents, out_over_extents);
116 
117   base_extents = {ExtentForRange(1, 2)};
118   over_extents = ByteToBitExtent({{0, 3 * 4096}, {4 * 4096, 4096}});
119   out_over_extents = ByteToBitExtent({{0, 3 * 4096}, {4 * 4096, 4096}});
120   EXPECT_FALSE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
121   EXPECT_EQ(over_extents, out_over_extents);
122 }
123 
124 TEST(DeflateUtilsTest, FindDeflatesTest) {
125   vector<Extent> extents = {
126       ExtentForRange(1, 1), ExtentForRange(3, 1), ExtentForRange(5, 1)};
127   vector<BitExtent> in_deflates = ByteToBitExtent({{0, 0},
128                                                    {10, 400},
129                                                    {4096, 0},
130                                                    {3000, 2000},
131                                                    {4096, 100},
132                                                    {4097, 100},
133                                                    {8100, 92},
134                                                    {8100, 93},
135                                                    {8100, 6000},
136                                                    {25000, 1}});
137   vector<BitExtent> expected_out_deflates =
138       ByteToBitExtent({{4096, 0}, {4096, 100}, {4097, 100}, {8100, 92}});
139   vector<BitExtent> out_deflates;
140   out_deflates = FindDeflates(extents, in_deflates);
141   EXPECT_EQ(out_deflates, expected_out_deflates);
142 }
143 
144 TEST(DeflateUtilsTest, FindDeflatesBoundaryTest) {
145   vector<Extent> extents = {};
146   vector<BitExtent> in_deflates = ByteToBitExtent({{0, 0}, {8100, 93}});
147   vector<BitExtent> expected_out_deflates = {};
148   vector<BitExtent> out_deflates;
149   out_deflates = FindDeflates(extents, in_deflates);
150   EXPECT_EQ(out_deflates, expected_out_deflates);
151 
152   extents = {};
153   in_deflates = {};
154   out_deflates = FindDeflates(extents, in_deflates);
155   EXPECT_EQ(out_deflates, expected_out_deflates);
156 }
157 
158 TEST(DeflateUtilsTest, CompactTest) {
159   vector<Extent> extents = {
160       ExtentForRange(1, 1), ExtentForRange(5, 1), ExtentForRange(3, 1)};
161   vector<BitExtent> in_deflates =
162       ByteToBitExtent({{4096, 0}, {12288, 4096}, {4096, 100}, {20480, 100}});
163   vector<BitExtent> expected_out_deflates =
164       ByteToBitExtent({{0, 0}, {0, 100}, {4096, 100}, {8192, 4096}});
165   vector<BitExtent> out_deflates;
166   ASSERT_TRUE(CompactDeflates(extents, in_deflates, &out_deflates));
167   EXPECT_EQ(out_deflates, expected_out_deflates);
168 }
169 
170 TEST(DeflateUtilsTest, CompactBoundaryTest) {
171   vector<Extent> extents = {};
172   vector<BitExtent> in_deflates = ByteToBitExtent({{4096, 0}});
173   vector<BitExtent> expected_out_deflates = {};
174   vector<BitExtent> out_deflates;
175   EXPECT_FALSE(CompactDeflates(extents, in_deflates, &out_deflates));
176   EXPECT_EQ(out_deflates, expected_out_deflates);
177 
178   extents = {};
179   in_deflates = {};
180   ASSERT_TRUE(CompactDeflates(extents, in_deflates, &out_deflates));
181   EXPECT_EQ(out_deflates, expected_out_deflates);
182 
183   extents = {ExtentForRange(1, 1)};
184   in_deflates = {};
185   ASSERT_TRUE(CompactDeflates(extents, in_deflates, &out_deflates));
186   EXPECT_EQ(out_deflates, expected_out_deflates);
187 }
188 
189 }  // namespace deflate_utils
190 }  // namespace chromeos_update_engine
191