backward_references_cost_enc.c 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790
  1. // Copyright 2017 Google Inc. All Rights Reserved.
  2. //
  3. // Use of this source code is governed by a BSD-style license
  4. // that can be found in the COPYING file in the root of the source
  5. // tree. An additional intellectual property rights grant can be found
  6. // in the file PATENTS. All contributing project authors may
  7. // be found in the AUTHORS file in the root of the source tree.
  8. // -----------------------------------------------------------------------------
  9. //
  10. // Improves a given set of backward references by analyzing its bit cost.
  11. // The algorithm is similar to the Zopfli compression algorithm but tailored to
  12. // images.
  13. //
  14. // Author: Vincent Rabaud (vrabaud@google.com)
  15. //
  16. #include <assert.h>
  17. #include "./backward_references_enc.h"
  18. #include "./histogram_enc.h"
  19. #include "../dsp/lossless_common.h"
  20. #include "../utils/color_cache_utils.h"
  21. #include "../utils/utils.h"
  22. #define VALUES_IN_BYTE 256
  23. extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs);
  24. extern int VP8LDistanceToPlaneCode(int xsize, int dist);
  25. extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs,
  26. const PixOrCopy v);
  27. typedef struct {
  28. double alpha_[VALUES_IN_BYTE];
  29. double red_[VALUES_IN_BYTE];
  30. double blue_[VALUES_IN_BYTE];
  31. double distance_[NUM_DISTANCE_CODES];
  32. double* literal_;
  33. } CostModel;
  34. static void ConvertPopulationCountTableToBitEstimates(
  35. int num_symbols, const uint32_t population_counts[], double output[]) {
  36. uint32_t sum = 0;
  37. int nonzeros = 0;
  38. int i;
  39. for (i = 0; i < num_symbols; ++i) {
  40. sum += population_counts[i];
  41. if (population_counts[i] > 0) {
  42. ++nonzeros;
  43. }
  44. }
  45. if (nonzeros <= 1) {
  46. memset(output, 0, num_symbols * sizeof(*output));
  47. } else {
  48. const double logsum = VP8LFastLog2(sum);
  49. for (i = 0; i < num_symbols; ++i) {
  50. output[i] = logsum - VP8LFastLog2(population_counts[i]);
  51. }
  52. }
  53. }
  54. static int CostModelBuild(CostModel* const m, int xsize, int cache_bits,
  55. const VP8LBackwardRefs* const refs) {
  56. int ok = 0;
  57. VP8LRefsCursor c = VP8LRefsCursorInit(refs);
  58. VP8LHistogram* const histo = VP8LAllocateHistogram(cache_bits);
  59. if (histo == NULL) goto Error;
  60. // The following code is similar to VP8LHistogramCreate but converts the
  61. // distance to plane code.
  62. VP8LHistogramInit(histo, cache_bits, /*init_arrays=*/ 1);
  63. while (VP8LRefsCursorOk(&c)) {
  64. VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos, VP8LDistanceToPlaneCode,
  65. xsize);
  66. VP8LRefsCursorNext(&c);
  67. }
  68. ConvertPopulationCountTableToBitEstimates(
  69. VP8LHistogramNumCodes(histo->palette_code_bits_),
  70. histo->literal_, m->literal_);
  71. ConvertPopulationCountTableToBitEstimates(
  72. VALUES_IN_BYTE, histo->red_, m->red_);
  73. ConvertPopulationCountTableToBitEstimates(
  74. VALUES_IN_BYTE, histo->blue_, m->blue_);
  75. ConvertPopulationCountTableToBitEstimates(
  76. VALUES_IN_BYTE, histo->alpha_, m->alpha_);
  77. ConvertPopulationCountTableToBitEstimates(
  78. NUM_DISTANCE_CODES, histo->distance_, m->distance_);
  79. ok = 1;
  80. Error:
  81. VP8LFreeHistogram(histo);
  82. return ok;
  83. }
  84. static WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) {
  85. return m->alpha_[v >> 24] +
  86. m->red_[(v >> 16) & 0xff] +
  87. m->literal_[(v >> 8) & 0xff] +
  88. m->blue_[v & 0xff];
  89. }
  90. static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) {
  91. const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx;
  92. return m->literal_[literal_idx];
  93. }
  94. static WEBP_INLINE double GetLengthCost(const CostModel* const m,
  95. uint32_t length) {
  96. int code, extra_bits;
  97. VP8LPrefixEncodeBits(length, &code, &extra_bits);
  98. return m->literal_[VALUES_IN_BYTE + code] + extra_bits;
  99. }
  100. static WEBP_INLINE double GetDistanceCost(const CostModel* const m,
  101. uint32_t distance) {
  102. int code, extra_bits;
  103. VP8LPrefixEncodeBits(distance, &code, &extra_bits);
  104. return m->distance_[code] + extra_bits;
  105. }
  106. static WEBP_INLINE void AddSingleLiteralWithCostModel(
  107. const uint32_t* const argb, VP8LColorCache* const hashers,
  108. const CostModel* const cost_model, int idx, int use_color_cache,
  109. float prev_cost, float* const cost, uint16_t* const dist_array) {
  110. double cost_val = prev_cost;
  111. const uint32_t color = argb[idx];
  112. const int ix = use_color_cache ? VP8LColorCacheContains(hashers, color) : -1;
  113. if (ix >= 0) {
  114. // use_color_cache is true and hashers contains color
  115. const double mul0 = 0.68;
  116. cost_val += GetCacheCost(cost_model, ix) * mul0;
  117. } else {
  118. const double mul1 = 0.82;
  119. if (use_color_cache) VP8LColorCacheInsert(hashers, color);
  120. cost_val += GetLiteralCost(cost_model, color) * mul1;
  121. }
  122. if (cost[idx] > cost_val) {
  123. cost[idx] = (float)cost_val;
  124. dist_array[idx] = 1; // only one is inserted.
  125. }
  126. }
  127. // -----------------------------------------------------------------------------
  128. // CostManager and interval handling
  129. // Empirical value to avoid high memory consumption but good for performance.
  130. #define COST_CACHE_INTERVAL_SIZE_MAX 500
  131. // To perform backward reference every pixel at index index_ is considered and
  132. // the cost for the MAX_LENGTH following pixels computed. Those following pixels
  133. // at index index_ + k (k from 0 to MAX_LENGTH) have a cost of:
  134. // cost_ = distance cost at index + GetLengthCost(cost_model, k)
  135. // and the minimum value is kept. GetLengthCost(cost_model, k) is cached in an
  136. // array of size MAX_LENGTH.
  137. // Instead of performing MAX_LENGTH comparisons per pixel, we keep track of the
  138. // minimal values using intervals of constant cost.
  139. // An interval is defined by the index_ of the pixel that generated it and
  140. // is only useful in a range of indices from start_ to end_ (exclusive), i.e.
  141. // it contains the minimum value for pixels between start_ and end_.
  142. // Intervals are stored in a linked list and ordered by start_. When a new
  143. // interval has a better value, old intervals are split or removed. There are
  144. // therefore no overlapping intervals.
  145. typedef struct CostInterval CostInterval;
  146. struct CostInterval {
  147. float cost_;
  148. int start_;
  149. int end_;
  150. int index_;
  151. CostInterval* previous_;
  152. CostInterval* next_;
  153. };
  154. // The GetLengthCost(cost_model, k) are cached in a CostCacheInterval.
  155. typedef struct {
  156. double cost_;
  157. int start_;
  158. int end_; // Exclusive.
  159. } CostCacheInterval;
  160. // This structure is in charge of managing intervals and costs.
  161. // It caches the different CostCacheInterval, caches the different
  162. // GetLengthCost(cost_model, k) in cost_cache_ and the CostInterval's (whose
  163. // count_ is limited by COST_CACHE_INTERVAL_SIZE_MAX).
  164. #define COST_MANAGER_MAX_FREE_LIST 10
  165. typedef struct {
  166. CostInterval* head_;
  167. int count_; // The number of stored intervals.
  168. CostCacheInterval* cache_intervals_;
  169. size_t cache_intervals_size_;
  170. double cost_cache_[MAX_LENGTH]; // Contains the GetLengthCost(cost_model, k).
  171. float* costs_;
  172. uint16_t* dist_array_;
  173. // Most of the time, we only need few intervals -> use a free-list, to avoid
  174. // fragmentation with small allocs in most common cases.
  175. CostInterval intervals_[COST_MANAGER_MAX_FREE_LIST];
  176. CostInterval* free_intervals_;
  177. // These are regularly malloc'd remains. This list can't grow larger than than
  178. // size COST_CACHE_INTERVAL_SIZE_MAX - COST_MANAGER_MAX_FREE_LIST, note.
  179. CostInterval* recycled_intervals_;
  180. } CostManager;
  181. static void CostIntervalAddToFreeList(CostManager* const manager,
  182. CostInterval* const interval) {
  183. interval->next_ = manager->free_intervals_;
  184. manager->free_intervals_ = interval;
  185. }
  186. static int CostIntervalIsInFreeList(const CostManager* const manager,
  187. const CostInterval* const interval) {
  188. return (interval >= &manager->intervals_[0] &&
  189. interval <= &manager->intervals_[COST_MANAGER_MAX_FREE_LIST - 1]);
  190. }
  191. static void CostManagerInitFreeList(CostManager* const manager) {
  192. int i;
  193. manager->free_intervals_ = NULL;
  194. for (i = 0; i < COST_MANAGER_MAX_FREE_LIST; ++i) {
  195. CostIntervalAddToFreeList(manager, &manager->intervals_[i]);
  196. }
  197. }
  198. static void DeleteIntervalList(CostManager* const manager,
  199. const CostInterval* interval) {
  200. while (interval != NULL) {
  201. const CostInterval* const next = interval->next_;
  202. if (!CostIntervalIsInFreeList(manager, interval)) {
  203. WebPSafeFree((void*)interval);
  204. } // else: do nothing
  205. interval = next;
  206. }
  207. }
  208. static void CostManagerClear(CostManager* const manager) {
  209. if (manager == NULL) return;
  210. WebPSafeFree(manager->costs_);
  211. WebPSafeFree(manager->cache_intervals_);
  212. // Clear the interval lists.
  213. DeleteIntervalList(manager, manager->head_);
  214. manager->head_ = NULL;
  215. DeleteIntervalList(manager, manager->recycled_intervals_);
  216. manager->recycled_intervals_ = NULL;
  217. // Reset pointers, count_ and cache_intervals_size_.
  218. memset(manager, 0, sizeof(*manager));
  219. CostManagerInitFreeList(manager);
  220. }
  221. static int CostManagerInit(CostManager* const manager,
  222. uint16_t* const dist_array, int pix_count,
  223. const CostModel* const cost_model) {
  224. int i;
  225. const int cost_cache_size = (pix_count > MAX_LENGTH) ? MAX_LENGTH : pix_count;
  226. manager->costs_ = NULL;
  227. manager->cache_intervals_ = NULL;
  228. manager->head_ = NULL;
  229. manager->recycled_intervals_ = NULL;
  230. manager->count_ = 0;
  231. manager->dist_array_ = dist_array;
  232. CostManagerInitFreeList(manager);
  233. // Fill in the cost_cache_.
  234. manager->cache_intervals_size_ = 1;
  235. manager->cost_cache_[0] = GetLengthCost(cost_model, 0);
  236. for (i = 1; i < cost_cache_size; ++i) {
  237. manager->cost_cache_[i] = GetLengthCost(cost_model, i);
  238. // Get the number of bound intervals.
  239. if (manager->cost_cache_[i] != manager->cost_cache_[i - 1]) {
  240. ++manager->cache_intervals_size_;
  241. }
  242. }
  243. // With the current cost model, we usually have below 20 intervals.
  244. // The worst case scenario with a cost model would be if every length has a
  245. // different cost, hence MAX_LENGTH but that is impossible with the current
  246. // implementation that spirals around a pixel.
  247. assert(manager->cache_intervals_size_ <= MAX_LENGTH);
  248. manager->cache_intervals_ = (CostCacheInterval*)WebPSafeMalloc(
  249. manager->cache_intervals_size_, sizeof(*manager->cache_intervals_));
  250. if (manager->cache_intervals_ == NULL) {
  251. CostManagerClear(manager);
  252. return 0;
  253. }
  254. // Fill in the cache_intervals_.
  255. {
  256. CostCacheInterval* cur = manager->cache_intervals_;
  257. // Consecutive values in cost_cache_ are compared and if a big enough
  258. // difference is found, a new interval is created and bounded.
  259. cur->start_ = 0;
  260. cur->end_ = 1;
  261. cur->cost_ = manager->cost_cache_[0];
  262. for (i = 1; i < cost_cache_size; ++i) {
  263. const double cost_val = manager->cost_cache_[i];
  264. if (cost_val != cur->cost_) {
  265. ++cur;
  266. // Initialize an interval.
  267. cur->start_ = i;
  268. cur->cost_ = cost_val;
  269. }
  270. cur->end_ = i + 1;
  271. }
  272. }
  273. manager->costs_ = (float*)WebPSafeMalloc(pix_count, sizeof(*manager->costs_));
  274. if (manager->costs_ == NULL) {
  275. CostManagerClear(manager);
  276. return 0;
  277. }
  278. // Set the initial costs_ high for every pixel as we will keep the minimum.
  279. for (i = 0; i < pix_count; ++i) manager->costs_[i] = 1e38f;
  280. return 1;
  281. }
  282. // Given the cost and the position that define an interval, update the cost at
  283. // pixel 'i' if it is smaller than the previously computed value.
  284. static WEBP_INLINE void UpdateCost(CostManager* const manager, int i,
  285. int position, float cost) {
  286. const int k = i - position;
  287. assert(k >= 0 && k < MAX_LENGTH);
  288. if (manager->costs_[i] > cost) {
  289. manager->costs_[i] = cost;
  290. manager->dist_array_[i] = k + 1;
  291. }
  292. }
  293. // Given the cost and the position that define an interval, update the cost for
  294. // all the pixels between 'start' and 'end' excluded.
  295. static WEBP_INLINE void UpdateCostPerInterval(CostManager* const manager,
  296. int start, int end, int position,
  297. float cost) {
  298. int i;
  299. for (i = start; i < end; ++i) UpdateCost(manager, i, position, cost);
  300. }
  301. // Given two intervals, make 'prev' be the previous one of 'next' in 'manager'.
  302. static WEBP_INLINE void ConnectIntervals(CostManager* const manager,
  303. CostInterval* const prev,
  304. CostInterval* const next) {
  305. if (prev != NULL) {
  306. prev->next_ = next;
  307. } else {
  308. manager->head_ = next;
  309. }
  310. if (next != NULL) next->previous_ = prev;
  311. }
  312. // Pop an interval in the manager.
  313. static WEBP_INLINE void PopInterval(CostManager* const manager,
  314. CostInterval* const interval) {
  315. if (interval == NULL) return;
  316. ConnectIntervals(manager, interval->previous_, interval->next_);
  317. if (CostIntervalIsInFreeList(manager, interval)) {
  318. CostIntervalAddToFreeList(manager, interval);
  319. } else { // recycle regularly malloc'd intervals too
  320. interval->next_ = manager->recycled_intervals_;
  321. manager->recycled_intervals_ = interval;
  322. }
  323. --manager->count_;
  324. assert(manager->count_ >= 0);
  325. }
  326. // Update the cost at index i by going over all the stored intervals that
  327. // overlap with i.
  328. // If 'do_clean_intervals' is set to something different than 0, intervals that
  329. // end before 'i' will be popped.
  330. static WEBP_INLINE void UpdateCostAtIndex(CostManager* const manager, int i,
  331. int do_clean_intervals) {
  332. CostInterval* current = manager->head_;
  333. while (current != NULL && current->start_ <= i) {
  334. CostInterval* const next = current->next_;
  335. if (current->end_ <= i) {
  336. if (do_clean_intervals) {
  337. // We have an outdated interval, remove it.
  338. PopInterval(manager, current);
  339. }
  340. } else {
  341. UpdateCost(manager, i, current->index_, current->cost_);
  342. }
  343. current = next;
  344. }
  345. }
  346. // Given a current orphan interval and its previous interval, before
  347. // it was orphaned (which can be NULL), set it at the right place in the list
  348. // of intervals using the start_ ordering and the previous interval as a hint.
  349. static WEBP_INLINE void PositionOrphanInterval(CostManager* const manager,
  350. CostInterval* const current,
  351. CostInterval* previous) {
  352. assert(current != NULL);
  353. if (previous == NULL) previous = manager->head_;
  354. while (previous != NULL && current->start_ < previous->start_) {
  355. previous = previous->previous_;
  356. }
  357. while (previous != NULL && previous->next_ != NULL &&
  358. previous->next_->start_ < current->start_) {
  359. previous = previous->next_;
  360. }
  361. if (previous != NULL) {
  362. ConnectIntervals(manager, current, previous->next_);
  363. } else {
  364. ConnectIntervals(manager, current, manager->head_);
  365. }
  366. ConnectIntervals(manager, previous, current);
  367. }
  368. // Insert an interval in the list contained in the manager by starting at
  369. // interval_in as a hint. The intervals are sorted by start_ value.
  370. static WEBP_INLINE void InsertInterval(CostManager* const manager,
  371. CostInterval* const interval_in,
  372. float cost, int position, int start,
  373. int end) {
  374. CostInterval* interval_new;
  375. if (start >= end) return;
  376. if (manager->count_ >= COST_CACHE_INTERVAL_SIZE_MAX) {
  377. // Serialize the interval if we cannot store it.
  378. UpdateCostPerInterval(manager, start, end, position, cost);
  379. return;
  380. }
  381. if (manager->free_intervals_ != NULL) {
  382. interval_new = manager->free_intervals_;
  383. manager->free_intervals_ = interval_new->next_;
  384. } else if (manager->recycled_intervals_ != NULL) {
  385. interval_new = manager->recycled_intervals_;
  386. manager->recycled_intervals_ = interval_new->next_;
  387. } else { // malloc for good
  388. interval_new = (CostInterval*)WebPSafeMalloc(1, sizeof(*interval_new));
  389. if (interval_new == NULL) {
  390. // Write down the interval if we cannot create it.
  391. UpdateCostPerInterval(manager, start, end, position, cost);
  392. return;
  393. }
  394. }
  395. interval_new->cost_ = cost;
  396. interval_new->index_ = position;
  397. interval_new->start_ = start;
  398. interval_new->end_ = end;
  399. PositionOrphanInterval(manager, interval_new, interval_in);
  400. ++manager->count_;
  401. }
  402. // Given a new cost interval defined by its start at position, its length value
  403. // and distance_cost, add its contributions to the previous intervals and costs.
  404. // If handling the interval or one of its subintervals becomes to heavy, its
  405. // contribution is added to the costs right away.
  406. static WEBP_INLINE void PushInterval(CostManager* const manager,
  407. double distance_cost, int position,
  408. int len) {
  409. size_t i;
  410. CostInterval* interval = manager->head_;
  411. CostInterval* interval_next;
  412. const CostCacheInterval* const cost_cache_intervals =
  413. manager->cache_intervals_;
  414. // If the interval is small enough, no need to deal with the heavy
  415. // interval logic, just serialize it right away. This constant is empirical.
  416. const int kSkipDistance = 10;
  417. if (len < kSkipDistance) {
  418. int j;
  419. for (j = position; j < position + len; ++j) {
  420. const int k = j - position;
  421. float cost_tmp;
  422. assert(k >= 0 && k < MAX_LENGTH);
  423. cost_tmp = (float)(distance_cost + manager->cost_cache_[k]);
  424. if (manager->costs_[j] > cost_tmp) {
  425. manager->costs_[j] = cost_tmp;
  426. manager->dist_array_[j] = k + 1;
  427. }
  428. }
  429. return;
  430. }
  431. for (i = 0; i < manager->cache_intervals_size_ &&
  432. cost_cache_intervals[i].start_ < len;
  433. ++i) {
  434. // Define the intersection of the ith interval with the new one.
  435. int start = position + cost_cache_intervals[i].start_;
  436. const int end = position + (cost_cache_intervals[i].end_ > len
  437. ? len
  438. : cost_cache_intervals[i].end_);
  439. const float cost = (float)(distance_cost + cost_cache_intervals[i].cost_);
  440. for (; interval != NULL && interval->start_ < end;
  441. interval = interval_next) {
  442. interval_next = interval->next_;
  443. // Make sure we have some overlap
  444. if (start >= interval->end_) continue;
  445. if (cost >= interval->cost_) {
  446. // When intervals are represented, the lower, the better.
  447. // [**********************************************************[
  448. // start end
  449. // [----------------------------------[
  450. // interval->start_ interval->end_
  451. // If we are worse than what we already have, add whatever we have so
  452. // far up to interval.
  453. const int start_new = interval->end_;
  454. InsertInterval(manager, interval, cost, position, start,
  455. interval->start_);
  456. start = start_new;
  457. if (start >= end) break;
  458. continue;
  459. }
  460. if (start <= interval->start_) {
  461. if (interval->end_ <= end) {
  462. // [----------------------------------[
  463. // interval->start_ interval->end_
  464. // [**************************************************************[
  465. // start end
  466. // We can safely remove the old interval as it is fully included.
  467. PopInterval(manager, interval);
  468. } else {
  469. // [------------------------------------[
  470. // interval->start_ interval->end_
  471. // [*****************************[
  472. // start end
  473. interval->start_ = end;
  474. break;
  475. }
  476. } else {
  477. if (end < interval->end_) {
  478. // [--------------------------------------------------------------[
  479. // interval->start_ interval->end_
  480. // [*****************************[
  481. // start end
  482. // We have to split the old interval as it fully contains the new one.
  483. const int end_original = interval->end_;
  484. interval->end_ = start;
  485. InsertInterval(manager, interval, interval->cost_, interval->index_,
  486. end, end_original);
  487. interval = interval->next_;
  488. break;
  489. } else {
  490. // [------------------------------------[
  491. // interval->start_ interval->end_
  492. // [*****************************[
  493. // start end
  494. interval->end_ = start;
  495. }
  496. }
  497. }
  498. // Insert the remaining interval from start to end.
  499. InsertInterval(manager, interval, cost, position, start, end);
  500. }
  501. }
  502. static int BackwardReferencesHashChainDistanceOnly(
  503. int xsize, int ysize, const uint32_t* const argb, int cache_bits,
  504. const VP8LHashChain* const hash_chain, const VP8LBackwardRefs* const refs,
  505. uint16_t* const dist_array) {
  506. int i;
  507. int ok = 0;
  508. int cc_init = 0;
  509. const int pix_count = xsize * ysize;
  510. const int use_color_cache = (cache_bits > 0);
  511. const size_t literal_array_size =
  512. sizeof(double) * (NUM_LITERAL_CODES + NUM_LENGTH_CODES +
  513. ((cache_bits > 0) ? (1 << cache_bits) : 0));
  514. const size_t cost_model_size = sizeof(CostModel) + literal_array_size;
  515. CostModel* const cost_model =
  516. (CostModel*)WebPSafeCalloc(1ULL, cost_model_size);
  517. VP8LColorCache hashers;
  518. CostManager* cost_manager =
  519. (CostManager*)WebPSafeMalloc(1ULL, sizeof(*cost_manager));
  520. int offset_prev = -1, len_prev = -1;
  521. double offset_cost = -1;
  522. int first_offset_is_constant = -1; // initialized with 'impossible' value
  523. int reach = 0;
  524. if (cost_model == NULL || cost_manager == NULL) goto Error;
  525. cost_model->literal_ = (double*)(cost_model + 1);
  526. if (use_color_cache) {
  527. cc_init = VP8LColorCacheInit(&hashers, cache_bits);
  528. if (!cc_init) goto Error;
  529. }
  530. if (!CostModelBuild(cost_model, xsize, cache_bits, refs)) {
  531. goto Error;
  532. }
  533. if (!CostManagerInit(cost_manager, dist_array, pix_count, cost_model)) {
  534. goto Error;
  535. }
  536. // We loop one pixel at a time, but store all currently best points to
  537. // non-processed locations from this point.
  538. dist_array[0] = 0;
  539. // Add first pixel as literal.
  540. AddSingleLiteralWithCostModel(argb, &hashers, cost_model, 0, use_color_cache,
  541. 0.f, cost_manager->costs_, dist_array);
  542. for (i = 1; i < pix_count; ++i) {
  543. const float prev_cost = cost_manager->costs_[i - 1];
  544. int offset, len;
  545. VP8LHashChainFindCopy(hash_chain, i, &offset, &len);
  546. // Try adding the pixel as a literal.
  547. AddSingleLiteralWithCostModel(argb, &hashers, cost_model, i,
  548. use_color_cache, prev_cost,
  549. cost_manager->costs_, dist_array);
  550. // If we are dealing with a non-literal.
  551. if (len >= 2) {
  552. if (offset != offset_prev) {
  553. const int code = VP8LDistanceToPlaneCode(xsize, offset);
  554. offset_cost = GetDistanceCost(cost_model, code);
  555. first_offset_is_constant = 1;
  556. PushInterval(cost_manager, prev_cost + offset_cost, i, len);
  557. } else {
  558. assert(offset_cost >= 0);
  559. assert(len_prev >= 0);
  560. assert(first_offset_is_constant == 0 || first_offset_is_constant == 1);
  561. // Instead of considering all contributions from a pixel i by calling:
  562. // PushInterval(cost_manager, prev_cost + offset_cost, i, len);
  563. // we optimize these contributions in case offset_cost stays the same
  564. // for consecutive pixels. This describes a set of pixels similar to a
  565. // previous set (e.g. constant color regions).
  566. if (first_offset_is_constant) {
  567. reach = i - 1 + len_prev - 1;
  568. first_offset_is_constant = 0;
  569. }
  570. if (i + len - 1 > reach) {
  571. // We can only be go further with the same offset if the previous
  572. // length was maxed, hence len_prev == len == MAX_LENGTH.
  573. // TODO(vrabaud), bump i to the end right away (insert cache and
  574. // update cost).
  575. // TODO(vrabaud), check if one of the points in between does not have
  576. // a lower cost.
  577. // Already consider the pixel at "reach" to add intervals that are
  578. // better than whatever we add.
  579. int offset_j, len_j = 0;
  580. int j;
  581. assert(len == MAX_LENGTH || len == pix_count - i);
  582. // Figure out the last consecutive pixel within [i, reach + 1] with
  583. // the same offset.
  584. for (j = i; j <= reach; ++j) {
  585. VP8LHashChainFindCopy(hash_chain, j + 1, &offset_j, &len_j);
  586. if (offset_j != offset) {
  587. VP8LHashChainFindCopy(hash_chain, j, &offset_j, &len_j);
  588. break;
  589. }
  590. }
  591. // Update the cost at j - 1 and j.
  592. UpdateCostAtIndex(cost_manager, j - 1, 0);
  593. UpdateCostAtIndex(cost_manager, j, 0);
  594. PushInterval(cost_manager, cost_manager->costs_[j - 1] + offset_cost,
  595. j, len_j);
  596. reach = j + len_j - 1;
  597. }
  598. }
  599. }
  600. UpdateCostAtIndex(cost_manager, i, 1);
  601. offset_prev = offset;
  602. len_prev = len;
  603. }
  604. ok = !refs->error_;
  605. Error:
  606. if (cc_init) VP8LColorCacheClear(&hashers);
  607. CostManagerClear(cost_manager);
  608. WebPSafeFree(cost_model);
  609. WebPSafeFree(cost_manager);
  610. return ok;
  611. }
  612. // We pack the path at the end of *dist_array and return
  613. // a pointer to this part of the array. Example:
  614. // dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232]
  615. static void TraceBackwards(uint16_t* const dist_array,
  616. int dist_array_size,
  617. uint16_t** const chosen_path,
  618. int* const chosen_path_size) {
  619. uint16_t* path = dist_array + dist_array_size;
  620. uint16_t* cur = dist_array + dist_array_size - 1;
  621. while (cur >= dist_array) {
  622. const int k = *cur;
  623. --path;
  624. *path = k;
  625. cur -= k;
  626. }
  627. *chosen_path = path;
  628. *chosen_path_size = (int)(dist_array + dist_array_size - path);
  629. }
  630. static int BackwardReferencesHashChainFollowChosenPath(
  631. const uint32_t* const argb, int cache_bits,
  632. const uint16_t* const chosen_path, int chosen_path_size,
  633. const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs) {
  634. const int use_color_cache = (cache_bits > 0);
  635. int ix;
  636. int i = 0;
  637. int ok = 0;
  638. int cc_init = 0;
  639. VP8LColorCache hashers;
  640. if (use_color_cache) {
  641. cc_init = VP8LColorCacheInit(&hashers, cache_bits);
  642. if (!cc_init) goto Error;
  643. }
  644. VP8LClearBackwardRefs(refs);
  645. for (ix = 0; ix < chosen_path_size; ++ix) {
  646. const int len = chosen_path[ix];
  647. if (len != 1) {
  648. int k;
  649. const int offset = VP8LHashChainFindOffset(hash_chain, i);
  650. VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len));
  651. if (use_color_cache) {
  652. for (k = 0; k < len; ++k) {
  653. VP8LColorCacheInsert(&hashers, argb[i + k]);
  654. }
  655. }
  656. i += len;
  657. } else {
  658. PixOrCopy v;
  659. const int idx =
  660. use_color_cache ? VP8LColorCacheContains(&hashers, argb[i]) : -1;
  661. if (idx >= 0) {
  662. // use_color_cache is true and hashers contains argb[i]
  663. // push pixel as a color cache index
  664. v = PixOrCopyCreateCacheIdx(idx);
  665. } else {
  666. if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
  667. v = PixOrCopyCreateLiteral(argb[i]);
  668. }
  669. VP8LBackwardRefsCursorAdd(refs, v);
  670. ++i;
  671. }
  672. }
  673. ok = !refs->error_;
  674. Error:
  675. if (cc_init) VP8LColorCacheClear(&hashers);
  676. return ok;
  677. }
  678. // Returns 1 on success.
  679. extern int VP8LBackwardReferencesTraceBackwards(
  680. int xsize, int ysize, const uint32_t* const argb, int cache_bits,
  681. const VP8LHashChain* const hash_chain,
  682. const VP8LBackwardRefs* const refs_src, VP8LBackwardRefs* const refs_dst);
  683. int VP8LBackwardReferencesTraceBackwards(int xsize, int ysize,
  684. const uint32_t* const argb,
  685. int cache_bits,
  686. const VP8LHashChain* const hash_chain,
  687. const VP8LBackwardRefs* const refs_src,
  688. VP8LBackwardRefs* const refs_dst) {
  689. int ok = 0;
  690. const int dist_array_size = xsize * ysize;
  691. uint16_t* chosen_path = NULL;
  692. int chosen_path_size = 0;
  693. uint16_t* dist_array =
  694. (uint16_t*)WebPSafeMalloc(dist_array_size, sizeof(*dist_array));
  695. if (dist_array == NULL) goto Error;
  696. if (!BackwardReferencesHashChainDistanceOnly(
  697. xsize, ysize, argb, cache_bits, hash_chain, refs_src, dist_array)) {
  698. goto Error;
  699. }
  700. TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size);
  701. if (!BackwardReferencesHashChainFollowChosenPath(
  702. argb, cache_bits, chosen_path, chosen_path_size, hash_chain,
  703. refs_dst)) {
  704. goto Error;
  705. }
  706. ok = 1;
  707. Error:
  708. WebPSafeFree(dist_array);
  709. return ok;
  710. }