13 #include <emmintrin.h>
24 static void storeUleb(vector<uint8_t>& result,
size_t value)
27 uint8_t b = value & 0x7F;
34 [[nodiscard]]
static constexpr
size_t loadUleb(
const uint8_t*& data)
40 result |= size_t(b & 0x7F) << shift;
41 if ((b & 0x80) == 0)
return result;
49 template<
int N>
bool comp(
const uint8_t* p,
const uint8_t* q);
51 template<>
bool comp<4>(
const uint8_t* p,
const uint8_t* q)
53 return *
reinterpret_cast<const uint32_t*
>(p) ==
54 *
reinterpret_cast<const uint32_t*
>(q);
57 template<>
bool comp<8>(
const uint8_t* p,
const uint8_t* q)
59 return *
reinterpret_cast<const uint64_t*
>(p) ==
60 *
reinterpret_cast<const uint64_t*
>(q);
64 template<>
bool comp<16>(
const uint8_t* p,
const uint8_t* q)
69 __m128i a = _mm_load_si128(
reinterpret_cast<const __m128i*
>(p));
70 __m128i b = _mm_load_si128(
reinterpret_cast<const __m128i*
>(q));
71 __m128i d = _mm_cmpeq_epi8(a, b);
72 return _mm_movemask_epi8(d) == 0xffff;
87 static std::pair<const uint8_t*, const uint8_t*> scan_mismatch(
88 const uint8_t* p,
const uint8_t* p_end,
const uint8_t* q,
const uint8_t* q_end)
90 assert((p_end - p) == (q_end - q));
96 constexpr
int WORD_SIZE =
105 if (
unlikely((p_end - p) < (2 * WORD_SIZE)) ||
106 unlikely((
reinterpret_cast<uintptr_t
>(p) & (WORD_SIZE - 1)) !=
107 (
reinterpret_cast<uintptr_t
>(q) & (WORD_SIZE - 1)))) {
112 if (
unlikely(
reinterpret_cast<uintptr_t
>(p) & (WORD_SIZE - 1))) {
114 if (*p != *q)
return {p, q};
116 }
while (
reinterpret_cast<uintptr_t
>(p) & (WORD_SIZE - 1));
124 auto* sentinel = &
const_cast<uint8_t*
>(p_end)[-WORD_SIZE];
125 auto save = *sentinel;
126 *sentinel = ~q_end[-WORD_SIZE];
128 while (comp<WORD_SIZE>(p, q)) {
129 p += WORD_SIZE; q += WORD_SIZE;
139 end:
return std::mismatch(p, p_end, q);
154 [[nodiscard]]
static constexpr std::pair<const uint8_t*, const uint8_t*> scan_match(
155 const uint8_t* p,
const uint8_t* p_end,
const uint8_t* q,
const uint8_t* q_end)
157 assert((p_end - p) == (q_end - q));
163 if (p == p_end)
return {p, q};
165 auto* p_last =
const_cast<uint8_t*
>(p_end - 1);
169 while (*p != *q) { ++p; ++q; }
172 if ((p == p_last) && (*p != *q)) { ++p; ++q; }
185 [[nodiscard]]
static vector<uint8_t> calcDelta(
186 const uint8_t* oldBuf,
const uint8_t* newBuf,
size_t size)
188 vector<uint8_t> result;
190 const auto* p = oldBuf;
191 const auto* q = newBuf;
192 const auto* p_end = p +
size;
193 const auto* q_end = q +
size;
197 std::tie(p, q) = scan_mismatch(p, p_end, q, q_end);
199 storeUleb(result, n1);
206 std::tie(p, q) = scan_match(p + 1, p_end, q + 1, q_end);
210 std::tie(p, q) = scan_mismatch(p, p_end, q, q_end);
212 if ((q != q_end) && (
n3 <= 2))
goto different;
214 storeUleb(result, n2);
215 result.insert(result.end(), q2, q3);
217 if (
n3 != 0) storeUleb(result,
n3);
220 result.shrink_to_fit();
225 static void applyDeltaInPlace(uint8_t* buf,
size_t size,
const uint8_t* delta)
230 auto n1 = loadUleb(delta);
232 if (buf ==
end)
break;
234 auto n2 = loadUleb(delta);
235 memcpy(buf, delta, n2);
247 globalAllocSize -= allocSize;
248 std::cout <<
"stat: ~DeltaBlock " << globalAllocSize
249 <<
" (-" << allocSize <<
")\n";
264 assert(!compressed());
267 globalAllocSize += allocSize;
268 std::cout <<
"stat: DeltaBlockCopy " << globalAllocSize
269 <<
" (+" << allocSize <<
")\n";
287 if (compressed())
return;
293 if (dstLen >=
size) {
297 compressedSize = dstLen;
299 block.
resize(compressedSize);
300 assert(compressed());
307 int delta = compressedSize - allocSize;
308 allocSize = compressedSize;
309 globalAllocSize += delta;
310 std::cout <<
"stat: compress " << globalAllocSize
311 <<
" (" << delta <<
")\n";
317 assert(!compressed());
325 std::shared_ptr<DeltaBlockCopy> prev_,
326 const uint8_t* data,
size_t size)
327 : prev(std::move(prev_))
328 , delta(calcDelta(prev->getData(), data,
size))
335 assert(memcmp(buf.data(), data,
size) == 0);
338 allocSize = delta.size();
339 globalAllocSize += allocSize;
340 std::cout <<
"stat: DeltaBlockDiff " << globalAllocSize
341 <<
" (+" << allocSize <<
")\n";
347 prev->apply(dst,
size);
348 applyDeltaInPlace(dst,
size, delta.data());
363 const void*
id,
const uint8_t* data,
size_t size)
366 [](
const Info& info,
const std::tuple<const void*, size_t>& info2) {
367 return std::tuple(info.id, info.size) < info2; });
368 if ((it ==
end(infos)) || (it->id != id) || (it->size !=
size)) {
370 it = infos.emplace(it,
id,
size);
372 assert(it->id ==
id);
373 assert(it->size ==
size);
375 auto ref = it->ref.lock();
376 if (it->accSize >=
size || !ref) {
384 auto b = std::make_shared<DeltaBlockCopy>(data,
size);
392 auto b = std::make_shared<DeltaBlockDiff>(ref, data,
size);
394 it->accSize += b->getDeltaSize();
400 const void*
id,
const uint8_t* data,
size_t size)
403 [](
const Info& info,
const void* id2) {
404 return info.id < id2; });
405 if ((it ==
end(infos)) || (it->id !=
id)) {
407 it = infos.emplace(it,
id,
size);
409 assert(it->size ==
size);
411 auto last = it->last.lock();
413 auto b = std::make_shared<DeltaBlockCopy>(data,
size);
428 for (
const Info& info : infos) {
429 if (
auto ref = info.ref.lock()) {
430 ref->compress(info.size);
const uint8_t * getData()
void apply(uint8_t *dst, size_t size) const override
DeltaBlockCopy(const uint8_t *data, size_t size)
void compress(size_t size)
void apply(uint8_t *dst, size_t size) const override
DeltaBlockDiff(std::shared_ptr< DeltaBlockCopy > prev_, const uint8_t *data, size_t size)
size_t getDeltaSize() const
virtual ~DeltaBlock()=default
std::shared_ptr< DeltaBlock > createNullDiff(const void *id, const uint8_t *data, size_t size)
std::shared_ptr< DeltaBlock > createNew(const void *id, const uint8_t *data, size_t size)
const T * data() const
Returns pointer to the start of the memory buffer.
void resize(size_t size)
Grow or shrink the memory block.
void swap(MemBuffer &other) noexcept
Swap the managed memory block of two MemBuffers.
static Sha1Sum calc(span< const uint8_t > data)
Easier to use interface, if you can pass all data in one go.
mat3 n3(vec3(1, 0, 3), vec3(4, 5, 6), vec3(7, 8, 9))
int compressBound(int iSize)
int decompress(const uint8_t *src, uint8_t *dst, int compressedSize, int dstCapacity)
int compress(const uint8_t *src, uint8_t *dst, int srcSize)
void save(unsigned width, unsigned height, const void **rowPointers, const PixelFormat &format, const std::string &filename)
This file implemented 3 utility functions:
bool comp< 4 >(const uint8_t *p, const uint8_t *q)
bool comp< 8 >(const uint8_t *p, const uint8_t *q)
AmdFlash::SectorInfo Info
bool comp(const uint8_t *p, const uint8_t *q)
auto lower_bound(ForwardRange &&range, const T &value)
size_t size(std::string_view utf8)
constexpr auto end(const zstring_view &x)