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.
ByteToBitExtent(const vector<ByteExtent> & byte_extents)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
TEST(DeflateUtilsTest,ExtentsShiftTest)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
TEST(DeflateUtilsTest,ShiftBitExtentsOverExtentsTest)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
TEST(DeflateUtilsTest,ShiftBitExtentsOverExtentsBoundaryTest)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
TEST(DeflateUtilsTest,FindDeflatesTest)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
TEST(DeflateUtilsTest,FindDeflatesBoundaryTest)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
TEST(DeflateUtilsTest,CompactTest)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
TEST(DeflateUtilsTest,CompactBoundaryTest)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