in Extended/libwebp/src/enc/backward_references_enc.c [526:673]
static int BackwardReferencesLz77Box(int xsize, int ysize,
const uint32_t* const argb, int cache_bits,
const VP8LHashChain* const hash_chain_best,
VP8LHashChain* hash_chain,
VP8LBackwardRefs* const refs) {
int i;
const int pix_count = xsize * ysize;
uint16_t* counts;
int window_offsets[WINDOW_OFFSETS_SIZE_MAX] = {0};
int window_offsets_new[WINDOW_OFFSETS_SIZE_MAX] = {0};
int window_offsets_size = 0;
int window_offsets_new_size = 0;
uint16_t* const counts_ini =
(uint16_t*)WebPSafeMalloc(xsize * ysize, sizeof(*counts_ini));
int best_offset_prev = -1, best_length_prev = -1;
if (counts_ini == NULL) return 0;
// counts[i] counts how many times a pixel is repeated starting at position i.
i = pix_count - 2;
counts = counts_ini + i;
counts[1] = 1;
for (; i >= 0; --i, --counts) {
if (argb[i] == argb[i + 1]) {
// Max out the counts to MAX_LENGTH.
counts[0] = counts[1] + (counts[1] != MAX_LENGTH);
} else {
counts[0] = 1;
}
}
// Figure out the window offsets around a pixel. They are stored in a
// spiraling order around the pixel as defined by VP8LDistanceToPlaneCode.
{
int x, y;
for (y = 0; y <= 6; ++y) {
for (x = -6; x <= 6; ++x) {
const int offset = y * xsize + x;
int plane_code;
// Ignore offsets that bring us after the pixel.
if (offset <= 0) continue;
plane_code = VP8LDistanceToPlaneCode(xsize, offset) - 1;
if (plane_code >= WINDOW_OFFSETS_SIZE_MAX) continue;
window_offsets[plane_code] = offset;
}
}
// For narrow images, not all plane codes are reached, so remove those.
for (i = 0; i < WINDOW_OFFSETS_SIZE_MAX; ++i) {
if (window_offsets[i] == 0) continue;
window_offsets[window_offsets_size++] = window_offsets[i];
}
// Given a pixel P, find the offsets that reach pixels unreachable from P-1
// with any of the offsets in window_offsets[].
for (i = 0; i < window_offsets_size; ++i) {
int j;
int is_reachable = 0;
for (j = 0; j < window_offsets_size && !is_reachable; ++j) {
is_reachable |= (window_offsets[i] == window_offsets[j] + 1);
}
if (!is_reachable) {
window_offsets_new[window_offsets_new_size] = window_offsets[i];
++window_offsets_new_size;
}
}
}
hash_chain->offset_length_[0] = 0;
for (i = 1; i < pix_count; ++i) {
int ind;
int best_length = VP8LHashChainFindLength(hash_chain_best, i);
int best_offset;
int do_compute = 1;
if (best_length >= MAX_LENGTH) {
// Do not recompute the best match if we already have a maximal one in the
// window.
best_offset = VP8LHashChainFindOffset(hash_chain_best, i);
for (ind = 0; ind < window_offsets_size; ++ind) {
if (best_offset == window_offsets[ind]) {
do_compute = 0;
break;
}
}
}
if (do_compute) {
// Figure out if we should use the offset/length from the previous pixel
// as an initial guess and therefore only inspect the offsets in
// window_offsets_new[].
const int use_prev =
(best_length_prev > 1) && (best_length_prev < MAX_LENGTH);
const int num_ind =
use_prev ? window_offsets_new_size : window_offsets_size;
best_length = use_prev ? best_length_prev - 1 : 0;
best_offset = use_prev ? best_offset_prev : 0;
// Find the longest match in a window around the pixel.
for (ind = 0; ind < num_ind; ++ind) {
int curr_length = 0;
int j = i;
int j_offset =
use_prev ? i - window_offsets_new[ind] : i - window_offsets[ind];
if (j_offset < 0 || argb[j_offset] != argb[i]) continue;
// The longest match is the sum of how many times each pixel is
// repeated.
do {
const int counts_j_offset = counts_ini[j_offset];
const int counts_j = counts_ini[j];
if (counts_j_offset != counts_j) {
curr_length +=
(counts_j_offset < counts_j) ? counts_j_offset : counts_j;
break;
}
// The same color is repeated counts_pos times at j_offset and j.
curr_length += counts_j_offset;
j_offset += counts_j_offset;
j += counts_j_offset;
} while (curr_length <= MAX_LENGTH && j < pix_count &&
argb[j_offset] == argb[j]);
if (best_length < curr_length) {
best_offset =
use_prev ? window_offsets_new[ind] : window_offsets[ind];
if (curr_length >= MAX_LENGTH) {
best_length = MAX_LENGTH;
break;
} else {
best_length = curr_length;
}
}
}
}
assert(i + best_length <= pix_count);
assert(best_length <= MAX_LENGTH);
if (best_length <= MIN_LENGTH) {
hash_chain->offset_length_[i] = 0;
best_offset_prev = 0;
best_length_prev = 0;
} else {
hash_chain->offset_length_[i] =
(best_offset << MAX_LENGTH_BITS) | (uint32_t)best_length;
best_offset_prev = best_offset;
best_length_prev = best_length;
}
}
hash_chain->offset_length_[0] = 0;
WebPSafeFree(counts_ini);
return BackwardReferencesLz77(xsize, ysize, argb, cache_bits, hash_chain,
refs);
}