deflate_utils_unittest.cc revision 3cd4df127c29eb90c0e203373edfbc9534c79169 
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
32using std::vector;
33using puffin::BitExtent;
34using puffin::ByteExtent;
35
36namespace chromeos_update_engine {
37namespace deflate_utils {
38
39// This creates a sudo-random BitExtents from ByteExtents for simpler testing.
40vector<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
49TEST(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
79TEST(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
93TEST(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
124TEST(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
144TEST(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
158TEST(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
170TEST(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