// Copyright 2017 The Chromium OS Authors. All rights reserved.
|
// Use of this source code is governed by a BSD-style license that can be
|
// found in the LICENSE file.
|
|
#include "puffin/src/include/puffin/utils.h"
|
|
#include <inttypes.h>
|
|
#include <algorithm>
|
#include <set>
|
#include <string>
|
#include <vector>
|
|
#include "puffin/src/bit_reader.h"
|
#include "puffin/src/file_stream.h"
|
#include "puffin/src/include/puffin/common.h"
|
#include "puffin/src/include/puffin/puffer.h"
|
#include "puffin/src/logging.h"
|
#include "puffin/src/memory_stream.h"
|
#include "puffin/src/puff_writer.h"
|
|
using std::set;
|
using std::string;
|
using std::vector;
|
|
namespace {
|
// Use memcpy to access the unaligned data of type |T|.
|
template <typename T>
|
inline T get_unaligned(const void* address) {
|
T result;
|
memcpy(&result, address, sizeof(T));
|
return result;
|
}
|
|
struct ExtentData {
|
puffin::BitExtent extent;
|
uint64_t byte_offset;
|
uint64_t byte_length;
|
const puffin::Buffer& data;
|
|
ExtentData(const puffin::BitExtent& in_extent, const puffin::Buffer& in_data)
|
: extent(in_extent), data(in_data) {
|
// Round start offset up and end offset down to exclude bits not in this
|
// extent. We simply ignore the bits at start and end that's not on byte
|
// boundary because as long as the majority of the bytes are the same,
|
// bsdiff will be able to reference it.
|
byte_offset = (extent.offset + 7) / 8;
|
uint64_t byte_end_offset = (extent.offset + extent.length) / 8;
|
CHECK(byte_end_offset <= data.size());
|
if (byte_end_offset > byte_offset) {
|
byte_length = byte_end_offset - byte_offset;
|
} else {
|
byte_length = 0;
|
}
|
}
|
|
int Compare(const ExtentData& other) const {
|
if (extent.length != other.extent.length) {
|
return extent.length < other.extent.length ? -1 : 1;
|
}
|
return memcmp(data.data() + byte_offset,
|
other.data.data() + other.byte_offset,
|
std::min(byte_length, other.byte_length));
|
}
|
bool operator<(const ExtentData& other) const { return Compare(other) < 0; }
|
bool operator==(const ExtentData& other) const { return Compare(other) == 0; }
|
};
|
|
} // namespace
|
|
namespace puffin {
|
|
bool LocateDeflatesInDeflateStream(const uint8_t* data,
|
uint64_t size,
|
uint64_t virtual_offset,
|
vector<BitExtent>* deflates,
|
uint64_t* compressed_size) {
|
Puffer puffer;
|
BufferBitReader bit_reader(data, size);
|
BufferPuffWriter puff_writer(nullptr, 0);
|
vector<BitExtent> sub_deflates;
|
TEST_AND_RETURN_FALSE(
|
puffer.PuffDeflate(&bit_reader, &puff_writer, &sub_deflates));
|
for (const auto& deflate : sub_deflates) {
|
deflates->emplace_back(deflate.offset + virtual_offset * 8, deflate.length);
|
}
|
if (compressed_size) {
|
*compressed_size = bit_reader.Offset();
|
}
|
return true;
|
}
|
|
// This function uses RFC1950 (https://www.ietf.org/rfc/rfc1950.txt) for the
|
// definition of a zlib stream. For finding the deflate blocks, we relying on
|
// the proper size of the zlib stream in |data|. Basically the size of the zlib
|
// stream should be known before hand. Otherwise we need to parse the stream and
|
// find the location of compressed blocks using CalculateSizeOfDeflateBlock().
|
bool LocateDeflatesInZlib(const Buffer& data, vector<BitExtent>* deflates) {
|
// A zlib stream has the following format:
|
// 0 1 compression method and flag
|
// 1 1 flag
|
// 2 4 preset dictionary (optional)
|
// 2 or 6 n compressed data
|
// n+(2 or 6) 4 Adler-32 checksum
|
TEST_AND_RETURN_FALSE(data.size() >= 6 + 4); // Header + Footer
|
uint16_t cmf = data[0];
|
auto compression_method = cmf & 0x0F;
|
// For deflate compression_method should be 8.
|
TEST_AND_RETURN_FALSE(compression_method == 8);
|
|
auto cinfo = (cmf & 0xF0) >> 4;
|
// Value greater than 7 is not allowed in deflate.
|
TEST_AND_RETURN_FALSE(cinfo <= 7);
|
|
auto flag = data[1];
|
TEST_AND_RETURN_FALSE(((cmf << 8) + flag) % 31 == 0);
|
|
uint64_t header_len = 2;
|
if (flag & 0x20) {
|
header_len += 4; // 4 bytes for the preset dictionary.
|
}
|
|
// 4 is for ADLER32.
|
TEST_AND_RETURN_FALSE(LocateDeflatesInDeflateStream(
|
data.data() + header_len, data.size() - header_len - 4, header_len,
|
deflates, nullptr));
|
return true;
|
}
|
|
bool FindDeflateSubBlocks(const UniqueStreamPtr& src,
|
const vector<ByteExtent>& deflates,
|
vector<BitExtent>* subblock_deflates) {
|
Puffer puffer;
|
Buffer deflate_buffer;
|
for (const auto& deflate : deflates) {
|
TEST_AND_RETURN_FALSE(src->Seek(deflate.offset));
|
// Read from src into deflate_buffer.
|
deflate_buffer.resize(deflate.length);
|
TEST_AND_RETURN_FALSE(src->Read(deflate_buffer.data(), deflate.length));
|
|
// Find all the subblocks.
|
BufferBitReader bit_reader(deflate_buffer.data(), deflate.length);
|
// The uncompressed blocks will be ignored since we are passing a null
|
// buffered puff writer and a valid deflate locations output array. This
|
// should not happen in the puffdiff or anywhere else by default.
|
BufferPuffWriter puff_writer(nullptr, 0);
|
vector<BitExtent> subblocks;
|
TEST_AND_RETURN_FALSE(
|
puffer.PuffDeflate(&bit_reader, &puff_writer, &subblocks));
|
TEST_AND_RETURN_FALSE(deflate.length == bit_reader.Offset());
|
for (const auto& subblock : subblocks) {
|
subblock_deflates->emplace_back(subblock.offset + deflate.offset * 8,
|
subblock.length);
|
}
|
}
|
return true;
|
}
|
|
bool LocateDeflatesInZlibBlocks(const string& file_path,
|
const vector<ByteExtent>& zlibs,
|
vector<BitExtent>* deflates) {
|
auto src = FileStream::Open(file_path, true, false);
|
TEST_AND_RETURN_FALSE(src);
|
|
Buffer buffer;
|
for (const auto& zlib : zlibs) {
|
buffer.resize(zlib.length);
|
TEST_AND_RETURN_FALSE(src->Seek(zlib.offset));
|
TEST_AND_RETURN_FALSE(src->Read(buffer.data(), buffer.size()));
|
vector<BitExtent> tmp_deflates;
|
TEST_AND_RETURN_FALSE(LocateDeflatesInZlib(buffer, &tmp_deflates));
|
for (const auto& deflate : tmp_deflates) {
|
deflates->emplace_back(deflate.offset + zlib.offset * 8, deflate.length);
|
}
|
}
|
return true;
|
}
|
|
// For more information about gzip format, refer to RFC 1952 located at:
|
// https://www.ietf.org/rfc/rfc1952.txt
|
bool LocateDeflatesInGzip(const Buffer& data, vector<BitExtent>* deflates) {
|
uint64_t member_start = 0;
|
while (member_start + 10 <= data.size() && data[member_start + 0] == 0x1F &&
|
data[member_start + 1] == 0x8B && data[member_start + 2] == 8) {
|
// Each member entry has the following format
|
// 0 1 0x1F
|
// 1 1 0x8B
|
// 2 1 compression method (8 denotes deflate)
|
// 3 1 set of flags
|
// 4 4 modification time
|
// 8 1 extra flags
|
// 9 1 operating system
|
|
uint64_t offset = member_start + 10;
|
int flag = data[member_start + 3];
|
// Extra field
|
if (flag & 4) {
|
TEST_AND_RETURN_FALSE(offset + 2 <= data.size());
|
uint16_t extra_length = data[offset++];
|
extra_length |= static_cast<uint16_t>(data[offset++]) << 8;
|
TEST_AND_RETURN_FALSE(offset + extra_length <= data.size());
|
offset += extra_length;
|
}
|
// File name field
|
if (flag & 8) {
|
while (true) {
|
TEST_AND_RETURN_FALSE(offset + 1 <= data.size());
|
if (data[offset++] == 0) {
|
break;
|
}
|
}
|
}
|
// File comment field
|
if (flag & 16) {
|
while (true) {
|
TEST_AND_RETURN_FALSE(offset + 1 <= data.size());
|
if (data[offset++] == 0) {
|
break;
|
}
|
}
|
}
|
// CRC16 field
|
if (flag & 2) {
|
offset += 2;
|
}
|
|
uint64_t compressed_size = 0;
|
TEST_AND_RETURN_FALSE(LocateDeflatesInDeflateStream(
|
data.data() + offset, data.size() - offset, offset, deflates,
|
&compressed_size));
|
offset += compressed_size;
|
|
// Ignore CRC32 and uncompressed size.
|
TEST_AND_RETURN_FALSE(offset + 8 <= data.size());
|
offset += 8;
|
member_start = offset;
|
}
|
// Return true if we've successfully parsed at least one gzip.
|
return member_start != 0;
|
}
|
|
// For more information about the zip format, refer to
|
// https://support.pkware.com/display/PKZIP/APPNOTE
|
bool LocateDeflatesInZipArchive(const Buffer& data,
|
vector<BitExtent>* deflates) {
|
uint64_t pos = 0;
|
while (pos <= data.size() - 30) {
|
// TODO(xunchang) add support for big endian system when searching for
|
// magic numbers.
|
if (get_unaligned<uint32_t>(data.data() + pos) != 0x04034b50) {
|
pos++;
|
continue;
|
}
|
|
// local file header format
|
// 0 4 0x04034b50
|
// 4 2 minimum version needed to extract
|
// 6 2 general purpose bit flag
|
// 8 2 compression method
|
// 10 4 file last modification date & time
|
// 14 4 CRC-32
|
// 18 4 compressed size
|
// 22 4 uncompressed size
|
// 26 2 file name length
|
// 28 2 extra field length
|
// 30 n file name
|
// 30+n m extra field
|
auto compression_method = get_unaligned<uint16_t>(data.data() + pos + 8);
|
if (compression_method != 8) { // non-deflate type
|
pos += 4;
|
continue;
|
}
|
|
auto compressed_size = get_unaligned<uint32_t>(data.data() + pos + 18);
|
auto file_name_length = get_unaligned<uint16_t>(data.data() + pos + 26);
|
auto extra_field_length = get_unaligned<uint16_t>(data.data() + pos + 28);
|
uint64_t header_size = 30 + file_name_length + extra_field_length;
|
|
// sanity check
|
if (static_cast<uint64_t>(header_size) + compressed_size > data.size() ||
|
pos > data.size() - header_size - compressed_size) {
|
pos += 4;
|
continue;
|
}
|
|
vector<BitExtent> tmp_deflates;
|
uint64_t offset = pos + header_size;
|
uint64_t calculated_compressed_size = 0;
|
if (!LocateDeflatesInDeflateStream(
|
data.data() + offset, data.size() - offset, offset, &tmp_deflates,
|
&calculated_compressed_size)) {
|
LOG(ERROR) << "Failed to decompress the zip entry starting from: " << pos
|
<< ", skip adding deflates for this entry.";
|
pos += 4;
|
continue;
|
}
|
|
// Double check the compressed size if it is available in the file header.
|
if (compressed_size > 0 && compressed_size != calculated_compressed_size) {
|
LOG(WARNING) << "Compressed size in the file header: " << compressed_size
|
<< " doesn't equal the real size: "
|
<< calculated_compressed_size;
|
}
|
|
deflates->insert(deflates->end(), tmp_deflates.begin(), tmp_deflates.end());
|
pos += header_size + calculated_compressed_size;
|
}
|
|
return true;
|
}
|
|
bool FindPuffLocations(const UniqueStreamPtr& src,
|
const vector<BitExtent>& deflates,
|
vector<ByteExtent>* puffs,
|
uint64_t* out_puff_size) {
|
Puffer puffer;
|
Buffer deflate_buffer;
|
|
// Here accumulate the size difference between each corresponding deflate and
|
// puff. At the end we add this cummulative size difference to the size of the
|
// deflate stream to get the size of the puff stream. We use signed size
|
// because puff size could be smaller than deflate size.
|
int64_t total_size_difference = 0;
|
for (auto deflate = deflates.begin(); deflate != deflates.end(); ++deflate) {
|
// Read from src into deflate_buffer.
|
auto start_byte = deflate->offset / 8;
|
auto end_byte = (deflate->offset + deflate->length + 7) / 8;
|
deflate_buffer.resize(end_byte - start_byte);
|
TEST_AND_RETURN_FALSE(src->Seek(start_byte));
|
TEST_AND_RETURN_FALSE(
|
src->Read(deflate_buffer.data(), deflate_buffer.size()));
|
// Find the size of the puff.
|
BufferBitReader bit_reader(deflate_buffer.data(), deflate_buffer.size());
|
uint64_t bits_to_skip = deflate->offset % 8;
|
TEST_AND_RETURN_FALSE(bit_reader.CacheBits(bits_to_skip));
|
bit_reader.DropBits(bits_to_skip);
|
|
BufferPuffWriter puff_writer(nullptr, 0);
|
TEST_AND_RETURN_FALSE(
|
puffer.PuffDeflate(&bit_reader, &puff_writer, nullptr));
|
TEST_AND_RETURN_FALSE(deflate_buffer.size() == bit_reader.Offset());
|
|
// 1 if a deflate ends at the same byte that the next deflate starts and
|
// there is a few bits gap between them. In practice this may never happen,
|
// but it is a good idea to support it anyways. If there is a gap, the value
|
// of the gap will be saved as an integer byte to the puff stream. The parts
|
// of the byte that belogs to the deflates are shifted out.
|
int gap = 0;
|
if (deflate != deflates.begin()) {
|
auto prev_deflate = std::prev(deflate);
|
if ((prev_deflate->offset + prev_deflate->length == deflate->offset)
|
// If deflates are on byte boundary the gap will not be counted later,
|
// so we won't worry about it.
|
&& (deflate->offset % 8 != 0)) {
|
gap = 1;
|
}
|
}
|
|
start_byte = ((deflate->offset + 7) / 8);
|
end_byte = (deflate->offset + deflate->length) / 8;
|
int64_t deflate_length_in_bytes = end_byte - start_byte;
|
|
// If there was no gap bits between the current and previous deflates, there
|
// will be no extra gap byte, so the offset will be shifted one byte back.
|
auto puff_offset = start_byte - gap + total_size_difference;
|
auto puff_size = puff_writer.Size();
|
// Add the location into puff.
|
puffs->emplace_back(puff_offset, puff_size);
|
total_size_difference +=
|
static_cast<int64_t>(puff_size) - deflate_length_in_bytes - gap;
|
}
|
|
uint64_t src_size;
|
TEST_AND_RETURN_FALSE(src->GetSize(&src_size));
|
auto final_size = static_cast<int64_t>(src_size) + total_size_difference;
|
TEST_AND_RETURN_FALSE(final_size >= 0);
|
*out_puff_size = final_size;
|
return true;
|
}
|
|
void RemoveEqualBitExtents(const Buffer& data1,
|
const Buffer& data2,
|
vector<BitExtent>* extents1,
|
vector<BitExtent>* extents2) {
|
set<ExtentData> extent1_set, equal_extents;
|
for (const BitExtent& ext : *extents1) {
|
extent1_set.emplace(ext, data1);
|
}
|
|
auto new_extents2_end = extents2->begin();
|
for (const BitExtent& ext : *extents2) {
|
ExtentData extent_data(ext, data2);
|
if (extent1_set.find(extent_data) != extent1_set.end()) {
|
equal_extents.insert(extent_data);
|
} else {
|
*new_extents2_end++ = ext;
|
}
|
}
|
extents2->erase(new_extents2_end, extents2->end());
|
extents1->erase(
|
std::remove_if(extents1->begin(), extents1->end(),
|
[&equal_extents, &data1](const BitExtent& ext) {
|
return equal_extents.find(ExtentData(ext, data1)) !=
|
equal_extents.end();
|
}),
|
extents1->end());
|
}
|
|
bool RemoveDeflatesWithBadDistanceCaches(const Buffer& data,
|
vector<BitExtent>* deflates) {
|
Puffer puffer(true /* exclude_bad_distance_caches */);
|
for (auto def = deflates->begin(); def != deflates->end();) {
|
uint64_t offset = def->offset / 8;
|
uint64_t length = (def->offset + def->length + 7) / 8 - offset;
|
BufferBitReader br(&data[offset], length);
|
BufferPuffWriter pw(nullptr, 0);
|
|
// Drop the first few bits in the buffer so we start exactly where the
|
// deflate starts.
|
uint64_t bits_to_drop = def->offset % 8;
|
TEST_AND_RETURN_FALSE(br.CacheBits(bits_to_drop));
|
br.DropBits(bits_to_drop);
|
|
vector<BitExtent> defs_out;
|
TEST_AND_RETURN_FALSE(puffer.PuffDeflate(&br, &pw, &defs_out));
|
|
TEST_AND_RETURN_FALSE(defs_out.size() <= 1);
|
if (defs_out.size() == 0) {
|
// This is a deflate we were looking for, remove it.
|
def = deflates->erase(def);
|
} else {
|
++def;
|
}
|
}
|
return true;
|
}
|
|
} // namespace puffin
|
