20static void storeUleb(std::vector<uint8_t>& result,
size_t value)
23 uint8_t b = value & 0x7F;
30[[nodiscard]]
static constexpr size_t loadUleb(std::span<const uint8_t>& data)
35 assert(!data.empty());
36 uint8_t b = data.front();
37 data = data.subspan(1);
38 result |= size_t(b & 0x7F) << shift;
39 if ((b & 0x80) == 0)
return result;
47template<
int N>
bool comp(
const uint8_t* p,
const uint8_t* q);
49template<>
bool comp<4>(
const uint8_t* p,
const uint8_t* q)
51 return *
reinterpret_cast<const uint32_t*
>(p) ==
52 *
reinterpret_cast<const uint32_t*
>(q);
55template<>
bool comp<8>(
const uint8_t* p,
const uint8_t* q)
57 return *
reinterpret_cast<const uint64_t*
>(p) ==
58 *
reinterpret_cast<const uint64_t*
>(q);
62template<>
bool comp<16>(
const uint8_t* p,
const uint8_t* q)
67 __m128i a = _mm_load_si128(
reinterpret_cast<const __m128i*
>(p));
68 __m128i b = _mm_load_si128(
reinterpret_cast<const __m128i*
>(q));
69 __m128i d = _mm_cmpeq_epi8(a, b);
70 return _mm_movemask_epi8(d) == 0xffff;
85static std::pair<const uint8_t*, const uint8_t*> scan_mismatch(
86 const uint8_t* p,
const uint8_t* p_end,
const uint8_t* q,
const uint8_t* q_end)
88 assert((p_end - p) == (q_end - q));
94 constexpr int WORD_SIZE =
103 if (((p_end - p) < (2 * WORD_SIZE)) ||
104 ((
reinterpret_cast<uintptr_t
>(p) & (WORD_SIZE - 1)) !=
105 (
reinterpret_cast<uintptr_t
>(q) & (WORD_SIZE - 1)))) [[unlikely]] {
110 if (
reinterpret_cast<uintptr_t
>(p) & (WORD_SIZE - 1)) [[unlikely]] {
112 if (*p != *q)
return {p, q};
114 }
while (
reinterpret_cast<uintptr_t
>(p) & (WORD_SIZE - 1));
122 auto* sentinel = &
const_cast<uint8_t*
>(p_end)[-WORD_SIZE];
123 auto save = *sentinel;
124 *sentinel = ~q_end[-WORD_SIZE];
126 while (comp<WORD_SIZE>(p, q)) {
127 p += WORD_SIZE; q += WORD_SIZE;
137end:
return std::mismatch(p, p_end, q);
152[[nodiscard]]
static constexpr std::pair<const uint8_t*, const uint8_t*> scan_match(
153 const uint8_t* p,
const uint8_t* p_end,
const uint8_t* q,
const uint8_t* q_end)
155 assert((p_end - p) == (q_end - q));
161 if (p == p_end)
return {p, q};
163 auto* p_last =
const_cast<uint8_t*
>(p_end - 1);
167 while (*p != *q) { ++p; ++q; }
170 if ((p == p_last) && (*p != *q)) { ++p; ++q; }
183[[nodiscard]]
static std::vector<uint8_t> calcDelta(
184 const uint8_t* oldBuf, std::span<const uint8_t> newBuf)
186 std::vector<uint8_t> result;
188 const auto* p = oldBuf;
189 const auto* q = newBuf.data();
190 auto size = newBuf.size();
191 const auto* p_end = p +
size;
192 const auto* q_end = q +
size;
196 std::tie(p, q) = scan_mismatch(p, p_end, q, q_end);
198 storeUleb(result, n1);
205 std::tie(p, q) = scan_match(p + 1, p_end, q + 1, q_end);
209 std::tie(p, q) = scan_mismatch(p, p_end, q, q_end);
211 if ((q != q_end) && (
n3 <= 2))
goto different;
213 storeUleb(result, n2);
214 result.insert(result.end(), q2, q3);
216 if (
n3 != 0) storeUleb(result,
n3);
219 result.shrink_to_fit();
224static void applyDeltaInPlace(std::span<uint8_t> buf, std::span<const uint8_t> delta)
226 while (!buf.empty()) {
227 auto n1 = loadUleb(delta);
228 buf = buf.subspan(n1);
229 if (buf.empty())
break;
231 auto n2 = loadUleb(delta);
233 buf = buf .subspan(n2);
234 delta = delta.subspan(n2);
244 globalAllocSize -= allocSize;
245 std::cout <<
"stat: ~DeltaBlock " << globalAllocSize
246 <<
" (-" << allocSize <<
")\n";
260 assert(!compressed());
263 globalAllocSize += allocSize;
264 std::cout <<
"stat: DeltaBlockCopy " << globalAllocSize
265 <<
" (+" << allocSize <<
")\n";
283 if (compressed())
return;
289 if (dstLen >=
size) {
293 compressedSize = dstLen;
295 block.
resize(compressedSize);
296 assert(compressed());
303 int delta = compressedSize - allocSize;
304 allocSize = compressedSize;
305 globalAllocSize += delta;
306 std::cout <<
"stat: compress " << globalAllocSize
307 <<
" (" << delta <<
")\n";
313 assert(!compressed());
321 std::shared_ptr<DeltaBlockCopy> prev_,
322 std::span<const uint8_t> data)
323 : prev(
std::move(prev_))
324 , delta(calcDelta(prev->getData(), data))
334 allocSize = delta.size();
335 globalAllocSize += allocSize;
336 std::cout <<
"stat: DeltaBlockDiff " << globalAllocSize
337 <<
" (+" << allocSize <<
")\n";
344 applyDeltaInPlace(dst, delta);
359 const void*
id, std::span<const uint8_t> data)
361 auto size = data.size();
363 [](
const Info& info) {
return std::tuple(info.id, info.size); });
364 if ((it ==
end(infos)) || (it->id !=
id) || (it->size !=
size)) {
366 it = infos.emplace(it,
id,
size);
368 assert(it->id ==
id);
369 assert(it->size ==
size);
371 auto ref = it->ref.lock();
372 if (it->accSize >=
size || !ref) {
380 auto b = std::make_shared<DeltaBlockCopy>(data);
388 auto b = std::make_shared<DeltaBlockDiff>(ref, data);
390 it->accSize += b->getDeltaSize();
396 const void*
id, std::span<const uint8_t> data)
398 auto size = data.size();
400 if ((it ==
end(infos)) || (it->id !=
id)) {
402 it = infos.emplace(it,
id,
size);
404 assert(it->size ==
size);
406 auto last = it->last.lock();
408 auto b = std::make_shared<DeltaBlockCopy>(data);
423 for (
const Info& info : infos) {
424 if (
auto ref = info.ref.lock()) {
425 ref->compress(info.size);
DeltaBlockCopy(std::span< const uint8_t > data)
const uint8_t * getData()
void apply(std::span< uint8_t > dst) const override
void compress(size_t size)
DeltaBlockDiff(std::shared_ptr< DeltaBlockCopy > prev_, std::span< const uint8_t > data)
void apply(std::span< uint8_t > dst) const override
size_t getDeltaSize() const
virtual ~DeltaBlock()=default
std::shared_ptr< DeltaBlock > createNew(const void *id, std::span< const uint8_t > data)
std::shared_ptr< DeltaBlock > createNullDiff(const void *id, std::span< const uint8_t > data)
void resize(size_t size)
Grow or shrink the memory block.
void swap(MemBuffer &other) noexcept
Swap the managed memory block of two MemBuffers.
const T * data() const
Returns pointer to the start of the memory buffer.
static Sha1Sum calc(std::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(size_t width, std::span< 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 copy(InputRange &&range, OutputIter out)
bool equal(InputRange1 &&range1, InputRange2 &&range2, Pred pred={}, Proj1 proj1={}, Proj2 proj2={})
auto lower_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
size_t size(std::string_view utf8)
constexpr auto end(const zstring_view &x)