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 std::vector; 33 using puffin::BitExtent; 34 using puffin::ByteExtent; 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
