histogram_enc.c 46 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252
  1. // Copyright 2012 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. // Author: Jyrki Alakuijala (jyrki@google.com)
  11. //
  12. #ifdef HAVE_CONFIG_H
  13. #include "../webp/config.h"
  14. #endif
  15. #include <math.h>
  16. #include "./backward_references_enc.h"
  17. #include "./histogram_enc.h"
  18. #include "../dsp/lossless.h"
  19. #include "../dsp/lossless_common.h"
  20. #include "../utils/utils.h"
  21. #define MAX_COST 1.e38
  22. // Number of partitions for the three dominant (literal, red and blue) symbol
  23. // costs.
  24. #define NUM_PARTITIONS 4
  25. // The size of the bin-hash corresponding to the three dominant costs.
  26. #define BIN_SIZE (NUM_PARTITIONS * NUM_PARTITIONS * NUM_PARTITIONS)
  27. // Maximum number of histograms allowed in greedy combining algorithm.
  28. #define MAX_HISTO_GREEDY 100
  29. static void HistogramClear(VP8LHistogram* const p) {
  30. uint32_t* const literal = p->literal_;
  31. const int cache_bits = p->palette_code_bits_;
  32. const int histo_size = VP8LGetHistogramSize(cache_bits);
  33. memset(p, 0, histo_size);
  34. p->palette_code_bits_ = cache_bits;
  35. p->literal_ = literal;
  36. }
  37. // Swap two histogram pointers.
  38. static void HistogramSwap(VP8LHistogram** const A, VP8LHistogram** const B) {
  39. VP8LHistogram* const tmp = *A;
  40. *A = *B;
  41. *B = tmp;
  42. }
  43. static void HistogramCopy(const VP8LHistogram* const src,
  44. VP8LHistogram* const dst) {
  45. uint32_t* const dst_literal = dst->literal_;
  46. const int dst_cache_bits = dst->palette_code_bits_;
  47. const int literal_size = VP8LHistogramNumCodes(dst_cache_bits);
  48. const int histo_size = VP8LGetHistogramSize(dst_cache_bits);
  49. assert(src->palette_code_bits_ == dst_cache_bits);
  50. memcpy(dst, src, histo_size);
  51. dst->literal_ = dst_literal;
  52. memcpy(dst->literal_, src->literal_, literal_size * sizeof(*dst->literal_));
  53. }
  54. int VP8LGetHistogramSize(int cache_bits) {
  55. const int literal_size = VP8LHistogramNumCodes(cache_bits);
  56. const size_t total_size = sizeof(VP8LHistogram) + sizeof(int) * literal_size;
  57. assert(total_size <= (size_t)0x7fffffff);
  58. return (int)total_size;
  59. }
  60. void VP8LFreeHistogram(VP8LHistogram* const histo) {
  61. WebPSafeFree(histo);
  62. }
  63. void VP8LFreeHistogramSet(VP8LHistogramSet* const histo) {
  64. WebPSafeFree(histo);
  65. }
  66. void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs,
  67. VP8LHistogram* const histo) {
  68. VP8LRefsCursor c = VP8LRefsCursorInit(refs);
  69. while (VP8LRefsCursorOk(&c)) {
  70. VP8LHistogramAddSinglePixOrCopy(histo, c.cur_pos, NULL, 0);
  71. VP8LRefsCursorNext(&c);
  72. }
  73. }
  74. void VP8LHistogramCreate(VP8LHistogram* const p,
  75. const VP8LBackwardRefs* const refs,
  76. int palette_code_bits) {
  77. if (palette_code_bits >= 0) {
  78. p->palette_code_bits_ = palette_code_bits;
  79. }
  80. HistogramClear(p);
  81. VP8LHistogramStoreRefs(refs, p);
  82. }
  83. void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits,
  84. int init_arrays) {
  85. p->palette_code_bits_ = palette_code_bits;
  86. if (init_arrays) {
  87. HistogramClear(p);
  88. } else {
  89. p->trivial_symbol_ = 0;
  90. p->bit_cost_ = 0.;
  91. p->literal_cost_ = 0.;
  92. p->red_cost_ = 0.;
  93. p->blue_cost_ = 0.;
  94. memset(p->is_used_, 0, sizeof(p->is_used_));
  95. }
  96. }
  97. VP8LHistogram* VP8LAllocateHistogram(int cache_bits) {
  98. VP8LHistogram* histo = NULL;
  99. const int total_size = VP8LGetHistogramSize(cache_bits);
  100. uint8_t* const memory = (uint8_t*)WebPSafeMalloc(total_size, sizeof(*memory));
  101. if (memory == NULL) return NULL;
  102. histo = (VP8LHistogram*)memory;
  103. // literal_ won't necessary be aligned.
  104. histo->literal_ = (uint32_t*)(memory + sizeof(VP8LHistogram));
  105. VP8LHistogramInit(histo, cache_bits, /*init_arrays=*/ 0);
  106. return histo;
  107. }
  108. // Resets the pointers of the histograms to point to the bit buffer in the set.
  109. static void HistogramSetResetPointers(VP8LHistogramSet* const set,
  110. int cache_bits) {
  111. int i;
  112. const int histo_size = VP8LGetHistogramSize(cache_bits);
  113. uint8_t* memory = (uint8_t*) (set->histograms);
  114. memory += set->max_size * sizeof(*set->histograms);
  115. for (i = 0; i < set->max_size; ++i) {
  116. memory = (uint8_t*) WEBP_ALIGN(memory);
  117. set->histograms[i] = (VP8LHistogram*) memory;
  118. // literal_ won't necessary be aligned.
  119. set->histograms[i]->literal_ = (uint32_t*)(memory + sizeof(VP8LHistogram));
  120. memory += histo_size;
  121. }
  122. }
  123. // Returns the total size of the VP8LHistogramSet.
  124. static size_t HistogramSetTotalSize(int size, int cache_bits) {
  125. const int histo_size = VP8LGetHistogramSize(cache_bits);
  126. return (sizeof(VP8LHistogramSet) + size * (sizeof(VP8LHistogram*) +
  127. histo_size + WEBP_ALIGN_CST));
  128. }
  129. VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits) {
  130. int i;
  131. VP8LHistogramSet* set;
  132. const size_t total_size = HistogramSetTotalSize(size, cache_bits);
  133. uint8_t* memory = (uint8_t*)WebPSafeMalloc(total_size, sizeof(*memory));
  134. if (memory == NULL) return NULL;
  135. set = (VP8LHistogramSet*)memory;
  136. memory += sizeof(*set);
  137. set->histograms = (VP8LHistogram**)memory;
  138. set->max_size = size;
  139. set->size = size;
  140. HistogramSetResetPointers(set, cache_bits);
  141. for (i = 0; i < size; ++i) {
  142. VP8LHistogramInit(set->histograms[i], cache_bits, /*init_arrays=*/ 0);
  143. }
  144. return set;
  145. }
  146. void VP8LHistogramSetClear(VP8LHistogramSet* const set) {
  147. int i;
  148. const int cache_bits = set->histograms[0]->palette_code_bits_;
  149. const int size = set->max_size;
  150. const size_t total_size = HistogramSetTotalSize(size, cache_bits);
  151. uint8_t* memory = (uint8_t*)set;
  152. memset(memory, 0, total_size);
  153. memory += sizeof(*set);
  154. set->histograms = (VP8LHistogram**)memory;
  155. set->max_size = size;
  156. set->size = size;
  157. HistogramSetResetPointers(set, cache_bits);
  158. for (i = 0; i < size; ++i) {
  159. set->histograms[i]->palette_code_bits_ = cache_bits;
  160. }
  161. }
  162. // Removes the histogram 'i' from 'set' by setting it to NULL.
  163. static void HistogramSetRemoveHistogram(VP8LHistogramSet* const set, int i,
  164. int* const num_used) {
  165. assert(set->histograms[i] != NULL);
  166. set->histograms[i] = NULL;
  167. --*num_used;
  168. // If we remove the last valid one, shrink until the next valid one.
  169. if (i == set->size - 1) {
  170. while (set->size >= 1 && set->histograms[set->size - 1] == NULL) {
  171. --set->size;
  172. }
  173. }
  174. }
  175. // -----------------------------------------------------------------------------
  176. void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo,
  177. const PixOrCopy* const v,
  178. int (*const distance_modifier)(int, int),
  179. int distance_modifier_arg0) {
  180. if (PixOrCopyIsLiteral(v)) {
  181. ++histo->alpha_[PixOrCopyLiteral(v, 3)];
  182. ++histo->red_[PixOrCopyLiteral(v, 2)];
  183. ++histo->literal_[PixOrCopyLiteral(v, 1)];
  184. ++histo->blue_[PixOrCopyLiteral(v, 0)];
  185. } else if (PixOrCopyIsCacheIdx(v)) {
  186. const int literal_ix =
  187. NUM_LITERAL_CODES + NUM_LENGTH_CODES + PixOrCopyCacheIdx(v);
  188. assert(histo->palette_code_bits_ != 0);
  189. ++histo->literal_[literal_ix];
  190. } else {
  191. int code, extra_bits;
  192. VP8LPrefixEncodeBits(PixOrCopyLength(v), &code, &extra_bits);
  193. ++histo->literal_[NUM_LITERAL_CODES + code];
  194. if (distance_modifier == NULL) {
  195. VP8LPrefixEncodeBits(PixOrCopyDistance(v), &code, &extra_bits);
  196. } else {
  197. VP8LPrefixEncodeBits(
  198. distance_modifier(distance_modifier_arg0, PixOrCopyDistance(v)),
  199. &code, &extra_bits);
  200. }
  201. ++histo->distance_[code];
  202. }
  203. }
  204. // -----------------------------------------------------------------------------
  205. // Entropy-related functions.
  206. static WEBP_INLINE double BitsEntropyRefine(const VP8LBitEntropy* entropy) {
  207. double mix;
  208. if (entropy->nonzeros < 5) {
  209. if (entropy->nonzeros <= 1) {
  210. return 0;
  211. }
  212. // Two symbols, they will be 0 and 1 in a Huffman code.
  213. // Let's mix in a bit of entropy to favor good clustering when
  214. // distributions of these are combined.
  215. if (entropy->nonzeros == 2) {
  216. return 0.99 * entropy->sum + 0.01 * entropy->entropy;
  217. }
  218. // No matter what the entropy says, we cannot be better than min_limit
  219. // with Huffman coding. I am mixing a bit of entropy into the
  220. // min_limit since it produces much better (~0.5 %) compression results
  221. // perhaps because of better entropy clustering.
  222. if (entropy->nonzeros == 3) {
  223. mix = 0.95;
  224. } else {
  225. mix = 0.7; // nonzeros == 4.
  226. }
  227. } else {
  228. mix = 0.627;
  229. }
  230. {
  231. double min_limit = 2 * entropy->sum - entropy->max_val;
  232. min_limit = mix * min_limit + (1.0 - mix) * entropy->entropy;
  233. return (entropy->entropy < min_limit) ? min_limit : entropy->entropy;
  234. }
  235. }
  236. double VP8LBitsEntropy(const uint32_t* const array, int n) {
  237. VP8LBitEntropy entropy;
  238. VP8LBitsEntropyUnrefined(array, n, &entropy);
  239. return BitsEntropyRefine(&entropy);
  240. }
  241. static double InitialHuffmanCost(void) {
  242. // Small bias because Huffman code length is typically not stored in
  243. // full length.
  244. static const int kHuffmanCodeOfHuffmanCodeSize = CODE_LENGTH_CODES * 3;
  245. static const double kSmallBias = 9.1;
  246. return kHuffmanCodeOfHuffmanCodeSize - kSmallBias;
  247. }
  248. // Finalize the Huffman cost based on streak numbers and length type (<3 or >=3)
  249. static double FinalHuffmanCost(const VP8LStreaks* const stats) {
  250. // The constants in this function are experimental and got rounded from
  251. // their original values in 1/8 when switched to 1/1024.
  252. double retval = InitialHuffmanCost();
  253. // Second coefficient: Many zeros in the histogram are covered efficiently
  254. // by a run-length encode. Originally 2/8.
  255. retval += stats->counts[0] * 1.5625 + 0.234375 * stats->streaks[0][1];
  256. // Second coefficient: Constant values are encoded less efficiently, but still
  257. // RLE'ed. Originally 6/8.
  258. retval += stats->counts[1] * 2.578125 + 0.703125 * stats->streaks[1][1];
  259. // 0s are usually encoded more efficiently than non-0s.
  260. // Originally 15/8.
  261. retval += 1.796875 * stats->streaks[0][0];
  262. // Originally 26/8.
  263. retval += 3.28125 * stats->streaks[1][0];
  264. return retval;
  265. }
  266. // Get the symbol entropy for the distribution 'population'.
  267. // Set 'trivial_sym', if there's only one symbol present in the distribution.
  268. static double PopulationCost(const uint32_t* const population, int length,
  269. uint32_t* const trivial_sym,
  270. uint8_t* const is_used) {
  271. VP8LBitEntropy bit_entropy;
  272. VP8LStreaks stats;
  273. VP8LGetEntropyUnrefined(population, length, &bit_entropy, &stats);
  274. if (trivial_sym != NULL) {
  275. *trivial_sym = (bit_entropy.nonzeros == 1) ? bit_entropy.nonzero_code
  276. : VP8L_NON_TRIVIAL_SYM;
  277. }
  278. // The histogram is used if there is at least one non-zero streak.
  279. *is_used = (stats.streaks[1][0] != 0 || stats.streaks[1][1] != 0);
  280. return BitsEntropyRefine(&bit_entropy) + FinalHuffmanCost(&stats);
  281. }
  282. // trivial_at_end is 1 if the two histograms only have one element that is
  283. // non-zero: both the zero-th one, or both the last one.
  284. static WEBP_INLINE double GetCombinedEntropy(const uint32_t* const X,
  285. const uint32_t* const Y,
  286. int length, int is_X_used,
  287. int is_Y_used,
  288. int trivial_at_end) {
  289. VP8LStreaks stats;
  290. if (trivial_at_end) {
  291. // This configuration is due to palettization that transforms an indexed
  292. // pixel into 0xff000000 | (pixel << 8) in VP8LBundleColorMap.
  293. // BitsEntropyRefine is 0 for histograms with only one non-zero value.
  294. // Only FinalHuffmanCost needs to be evaluated.
  295. memset(&stats, 0, sizeof(stats));
  296. // Deal with the non-zero value at index 0 or length-1.
  297. stats.streaks[1][0] = 1;
  298. // Deal with the following/previous zero streak.
  299. stats.counts[0] = 1;
  300. stats.streaks[0][1] = length - 1;
  301. return FinalHuffmanCost(&stats);
  302. } else {
  303. VP8LBitEntropy bit_entropy;
  304. if (is_X_used) {
  305. if (is_Y_used) {
  306. VP8LGetCombinedEntropyUnrefined(X, Y, length, &bit_entropy, &stats);
  307. } else {
  308. VP8LGetEntropyUnrefined(X, length, &bit_entropy, &stats);
  309. }
  310. } else {
  311. if (is_Y_used) {
  312. VP8LGetEntropyUnrefined(Y, length, &bit_entropy, &stats);
  313. } else {
  314. memset(&stats, 0, sizeof(stats));
  315. stats.counts[0] = 1;
  316. stats.streaks[0][length > 3] = length;
  317. VP8LBitEntropyInit(&bit_entropy);
  318. }
  319. }
  320. return BitsEntropyRefine(&bit_entropy) + FinalHuffmanCost(&stats);
  321. }
  322. }
  323. // Estimates the Entropy + Huffman + other block overhead size cost.
  324. double VP8LHistogramEstimateBits(VP8LHistogram* const p) {
  325. return
  326. PopulationCost(p->literal_, VP8LHistogramNumCodes(p->palette_code_bits_),
  327. NULL, &p->is_used_[0])
  328. + PopulationCost(p->red_, NUM_LITERAL_CODES, NULL, &p->is_used_[1])
  329. + PopulationCost(p->blue_, NUM_LITERAL_CODES, NULL, &p->is_used_[2])
  330. + PopulationCost(p->alpha_, NUM_LITERAL_CODES, NULL, &p->is_used_[3])
  331. + PopulationCost(p->distance_, NUM_DISTANCE_CODES, NULL, &p->is_used_[4])
  332. + VP8LExtraCost(p->literal_ + NUM_LITERAL_CODES, NUM_LENGTH_CODES)
  333. + VP8LExtraCost(p->distance_, NUM_DISTANCE_CODES);
  334. }
  335. // -----------------------------------------------------------------------------
  336. // Various histogram combine/cost-eval functions
  337. static int GetCombinedHistogramEntropy(const VP8LHistogram* const a,
  338. const VP8LHistogram* const b,
  339. double cost_threshold,
  340. double* cost) {
  341. const int palette_code_bits = a->palette_code_bits_;
  342. int trivial_at_end = 0;
  343. assert(a->palette_code_bits_ == b->palette_code_bits_);
  344. *cost += GetCombinedEntropy(a->literal_, b->literal_,
  345. VP8LHistogramNumCodes(palette_code_bits),
  346. a->is_used_[0], b->is_used_[0], 0);
  347. *cost += VP8LExtraCostCombined(a->literal_ + NUM_LITERAL_CODES,
  348. b->literal_ + NUM_LITERAL_CODES,
  349. NUM_LENGTH_CODES);
  350. if (*cost > cost_threshold) return 0;
  351. if (a->trivial_symbol_ != VP8L_NON_TRIVIAL_SYM &&
  352. a->trivial_symbol_ == b->trivial_symbol_) {
  353. // A, R and B are all 0 or 0xff.
  354. const uint32_t color_a = (a->trivial_symbol_ >> 24) & 0xff;
  355. const uint32_t color_r = (a->trivial_symbol_ >> 16) & 0xff;
  356. const uint32_t color_b = (a->trivial_symbol_ >> 0) & 0xff;
  357. if ((color_a == 0 || color_a == 0xff) &&
  358. (color_r == 0 || color_r == 0xff) &&
  359. (color_b == 0 || color_b == 0xff)) {
  360. trivial_at_end = 1;
  361. }
  362. }
  363. *cost +=
  364. GetCombinedEntropy(a->red_, b->red_, NUM_LITERAL_CODES, a->is_used_[1],
  365. b->is_used_[1], trivial_at_end);
  366. if (*cost > cost_threshold) return 0;
  367. *cost +=
  368. GetCombinedEntropy(a->blue_, b->blue_, NUM_LITERAL_CODES, a->is_used_[2],
  369. b->is_used_[2], trivial_at_end);
  370. if (*cost > cost_threshold) return 0;
  371. *cost +=
  372. GetCombinedEntropy(a->alpha_, b->alpha_, NUM_LITERAL_CODES,
  373. a->is_used_[3], b->is_used_[3], trivial_at_end);
  374. if (*cost > cost_threshold) return 0;
  375. *cost +=
  376. GetCombinedEntropy(a->distance_, b->distance_, NUM_DISTANCE_CODES,
  377. a->is_used_[4], b->is_used_[4], 0);
  378. *cost +=
  379. VP8LExtraCostCombined(a->distance_, b->distance_, NUM_DISTANCE_CODES);
  380. if (*cost > cost_threshold) return 0;
  381. return 1;
  382. }
  383. static WEBP_INLINE void HistogramAdd(const VP8LHistogram* const a,
  384. const VP8LHistogram* const b,
  385. VP8LHistogram* const out) {
  386. VP8LHistogramAdd(a, b, out);
  387. out->trivial_symbol_ = (a->trivial_symbol_ == b->trivial_symbol_)
  388. ? a->trivial_symbol_
  389. : VP8L_NON_TRIVIAL_SYM;
  390. }
  391. // Performs out = a + b, computing the cost C(a+b) - C(a) - C(b) while comparing
  392. // to the threshold value 'cost_threshold'. The score returned is
  393. // Score = C(a+b) - C(a) - C(b), where C(a) + C(b) is known and fixed.
  394. // Since the previous score passed is 'cost_threshold', we only need to compare
  395. // the partial cost against 'cost_threshold + C(a) + C(b)' to possibly bail-out
  396. // early.
  397. static double HistogramAddEval(const VP8LHistogram* const a,
  398. const VP8LHistogram* const b,
  399. VP8LHistogram* const out,
  400. double cost_threshold) {
  401. double cost = 0;
  402. const double sum_cost = a->bit_cost_ + b->bit_cost_;
  403. cost_threshold += sum_cost;
  404. if (GetCombinedHistogramEntropy(a, b, cost_threshold, &cost)) {
  405. HistogramAdd(a, b, out);
  406. out->bit_cost_ = cost;
  407. out->palette_code_bits_ = a->palette_code_bits_;
  408. }
  409. return cost - sum_cost;
  410. }
  411. // Same as HistogramAddEval(), except that the resulting histogram
  412. // is not stored. Only the cost C(a+b) - C(a) is evaluated. We omit
  413. // the term C(b) which is constant over all the evaluations.
  414. static double HistogramAddThresh(const VP8LHistogram* const a,
  415. const VP8LHistogram* const b,
  416. double cost_threshold) {
  417. double cost;
  418. assert(a != NULL && b != NULL);
  419. cost = -a->bit_cost_;
  420. GetCombinedHistogramEntropy(a, b, cost_threshold, &cost);
  421. return cost;
  422. }
  423. // -----------------------------------------------------------------------------
  424. // The structure to keep track of cost range for the three dominant entropy
  425. // symbols.
  426. // TODO(skal): Evaluate if float can be used here instead of double for
  427. // representing the entropy costs.
  428. typedef struct {
  429. double literal_max_;
  430. double literal_min_;
  431. double red_max_;
  432. double red_min_;
  433. double blue_max_;
  434. double blue_min_;
  435. } DominantCostRange;
  436. static void DominantCostRangeInit(DominantCostRange* const c) {
  437. c->literal_max_ = 0.;
  438. c->literal_min_ = MAX_COST;
  439. c->red_max_ = 0.;
  440. c->red_min_ = MAX_COST;
  441. c->blue_max_ = 0.;
  442. c->blue_min_ = MAX_COST;
  443. }
  444. static void UpdateDominantCostRange(
  445. const VP8LHistogram* const h, DominantCostRange* const c) {
  446. if (c->literal_max_ < h->literal_cost_) c->literal_max_ = h->literal_cost_;
  447. if (c->literal_min_ > h->literal_cost_) c->literal_min_ = h->literal_cost_;
  448. if (c->red_max_ < h->red_cost_) c->red_max_ = h->red_cost_;
  449. if (c->red_min_ > h->red_cost_) c->red_min_ = h->red_cost_;
  450. if (c->blue_max_ < h->blue_cost_) c->blue_max_ = h->blue_cost_;
  451. if (c->blue_min_ > h->blue_cost_) c->blue_min_ = h->blue_cost_;
  452. }
  453. static void UpdateHistogramCost(VP8LHistogram* const h) {
  454. uint32_t alpha_sym, red_sym, blue_sym;
  455. const double alpha_cost =
  456. PopulationCost(h->alpha_, NUM_LITERAL_CODES, &alpha_sym,
  457. &h->is_used_[3]);
  458. const double distance_cost =
  459. PopulationCost(h->distance_, NUM_DISTANCE_CODES, NULL, &h->is_used_[4]) +
  460. VP8LExtraCost(h->distance_, NUM_DISTANCE_CODES);
  461. const int num_codes = VP8LHistogramNumCodes(h->palette_code_bits_);
  462. h->literal_cost_ =
  463. PopulationCost(h->literal_, num_codes, NULL, &h->is_used_[0]) +
  464. VP8LExtraCost(h->literal_ + NUM_LITERAL_CODES, NUM_LENGTH_CODES);
  465. h->red_cost_ =
  466. PopulationCost(h->red_, NUM_LITERAL_CODES, &red_sym, &h->is_used_[1]);
  467. h->blue_cost_ =
  468. PopulationCost(h->blue_, NUM_LITERAL_CODES, &blue_sym, &h->is_used_[2]);
  469. h->bit_cost_ = h->literal_cost_ + h->red_cost_ + h->blue_cost_ +
  470. alpha_cost + distance_cost;
  471. if ((alpha_sym | red_sym | blue_sym) == VP8L_NON_TRIVIAL_SYM) {
  472. h->trivial_symbol_ = VP8L_NON_TRIVIAL_SYM;
  473. } else {
  474. h->trivial_symbol_ =
  475. ((uint32_t)alpha_sym << 24) | (red_sym << 16) | (blue_sym << 0);
  476. }
  477. }
  478. static int GetBinIdForEntropy(double min, double max, double val) {
  479. const double range = max - min;
  480. if (range > 0.) {
  481. const double delta = val - min;
  482. return (int)((NUM_PARTITIONS - 1e-6) * delta / range);
  483. } else {
  484. return 0;
  485. }
  486. }
  487. static int GetHistoBinIndex(const VP8LHistogram* const h,
  488. const DominantCostRange* const c, int low_effort) {
  489. int bin_id = GetBinIdForEntropy(c->literal_min_, c->literal_max_,
  490. h->literal_cost_);
  491. assert(bin_id < NUM_PARTITIONS);
  492. if (!low_effort) {
  493. bin_id = bin_id * NUM_PARTITIONS
  494. + GetBinIdForEntropy(c->red_min_, c->red_max_, h->red_cost_);
  495. bin_id = bin_id * NUM_PARTITIONS
  496. + GetBinIdForEntropy(c->blue_min_, c->blue_max_, h->blue_cost_);
  497. assert(bin_id < BIN_SIZE);
  498. }
  499. return bin_id;
  500. }
  501. // Construct the histograms from backward references.
  502. static void HistogramBuild(
  503. int xsize, int histo_bits, const VP8LBackwardRefs* const backward_refs,
  504. VP8LHistogramSet* const image_histo) {
  505. int x = 0, y = 0;
  506. const int histo_xsize = VP8LSubSampleSize(xsize, histo_bits);
  507. VP8LHistogram** const histograms = image_histo->histograms;
  508. VP8LRefsCursor c = VP8LRefsCursorInit(backward_refs);
  509. assert(histo_bits > 0);
  510. VP8LHistogramSetClear(image_histo);
  511. while (VP8LRefsCursorOk(&c)) {
  512. const PixOrCopy* const v = c.cur_pos;
  513. const int ix = (y >> histo_bits) * histo_xsize + (x >> histo_bits);
  514. VP8LHistogramAddSinglePixOrCopy(histograms[ix], v, NULL, 0);
  515. x += PixOrCopyLength(v);
  516. while (x >= xsize) {
  517. x -= xsize;
  518. ++y;
  519. }
  520. VP8LRefsCursorNext(&c);
  521. }
  522. }
  523. // Copies the histograms and computes its bit_cost.
  524. static const uint16_t kInvalidHistogramSymbol = (uint16_t)(-1);
  525. static void HistogramCopyAndAnalyze(VP8LHistogramSet* const orig_histo,
  526. VP8LHistogramSet* const image_histo,
  527. int* const num_used,
  528. uint16_t* const histogram_symbols) {
  529. int i, cluster_id;
  530. int num_used_orig = *num_used;
  531. VP8LHistogram** const orig_histograms = orig_histo->histograms;
  532. VP8LHistogram** const histograms = image_histo->histograms;
  533. assert(image_histo->max_size == orig_histo->max_size);
  534. for (cluster_id = 0, i = 0; i < orig_histo->max_size; ++i) {
  535. VP8LHistogram* const histo = orig_histograms[i];
  536. UpdateHistogramCost(histo);
  537. // Skip the histogram if it is completely empty, which can happen for tiles
  538. // with no information (when they are skipped because of LZ77).
  539. if (!histo->is_used_[0] && !histo->is_used_[1] && !histo->is_used_[2]
  540. && !histo->is_used_[3] && !histo->is_used_[4]) {
  541. // The first histogram is always used. If an histogram is empty, we set
  542. // its id to be the same as the previous one: this will improve
  543. // compressibility for later LZ77.
  544. assert(i > 0);
  545. HistogramSetRemoveHistogram(image_histo, i, num_used);
  546. HistogramSetRemoveHistogram(orig_histo, i, &num_used_orig);
  547. histogram_symbols[i] = kInvalidHistogramSymbol;
  548. } else {
  549. // Copy histograms from orig_histo[] to image_histo[].
  550. HistogramCopy(histo, histograms[i]);
  551. histogram_symbols[i] = cluster_id++;
  552. assert(cluster_id <= image_histo->max_size);
  553. }
  554. }
  555. }
  556. // Partition histograms to different entropy bins for three dominant (literal,
  557. // red and blue) symbol costs and compute the histogram aggregate bit_cost.
  558. static void HistogramAnalyzeEntropyBin(VP8LHistogramSet* const image_histo,
  559. uint16_t* const bin_map,
  560. int low_effort) {
  561. int i;
  562. VP8LHistogram** const histograms = image_histo->histograms;
  563. const int histo_size = image_histo->size;
  564. DominantCostRange cost_range;
  565. DominantCostRangeInit(&cost_range);
  566. // Analyze the dominant (literal, red and blue) entropy costs.
  567. for (i = 0; i < histo_size; ++i) {
  568. if (histograms[i] == NULL) continue;
  569. UpdateDominantCostRange(histograms[i], &cost_range);
  570. }
  571. // bin-hash histograms on three of the dominant (literal, red and blue)
  572. // symbol costs and store the resulting bin_id for each histogram.
  573. for (i = 0; i < histo_size; ++i) {
  574. // bin_map[i] is not set to a special value as its use will later be guarded
  575. // by another (histograms[i] == NULL).
  576. if (histograms[i] == NULL) continue;
  577. bin_map[i] = GetHistoBinIndex(histograms[i], &cost_range, low_effort);
  578. }
  579. }
  580. // Merges some histograms with same bin_id together if it's advantageous.
  581. // Sets the remaining histograms to NULL.
  582. static void HistogramCombineEntropyBin(VP8LHistogramSet* const image_histo,
  583. int* num_used,
  584. const uint16_t* const clusters,
  585. uint16_t* const cluster_mappings,
  586. VP8LHistogram* cur_combo,
  587. const uint16_t* const bin_map,
  588. int num_bins,
  589. double combine_cost_factor,
  590. int low_effort) {
  591. VP8LHistogram** const histograms = image_histo->histograms;
  592. int idx;
  593. struct {
  594. int16_t first; // position of the histogram that accumulates all
  595. // histograms with the same bin_id
  596. uint16_t num_combine_failures; // number of combine failures per bin_id
  597. } bin_info[BIN_SIZE];
  598. assert(num_bins <= BIN_SIZE);
  599. for (idx = 0; idx < num_bins; ++idx) {
  600. bin_info[idx].first = -1;
  601. bin_info[idx].num_combine_failures = 0;
  602. }
  603. // By default, a cluster matches itself.
  604. for (idx = 0; idx < *num_used; ++idx) cluster_mappings[idx] = idx;
  605. for (idx = 0; idx < image_histo->size; ++idx) {
  606. int bin_id, first;
  607. if (histograms[idx] == NULL) continue;
  608. bin_id = bin_map[idx];
  609. first = bin_info[bin_id].first;
  610. if (first == -1) {
  611. bin_info[bin_id].first = idx;
  612. } else if (low_effort) {
  613. HistogramAdd(histograms[idx], histograms[first], histograms[first]);
  614. HistogramSetRemoveHistogram(image_histo, idx, num_used);
  615. cluster_mappings[clusters[idx]] = clusters[first];
  616. } else {
  617. // try to merge #idx into #first (both share the same bin_id)
  618. const double bit_cost = histograms[idx]->bit_cost_;
  619. const double bit_cost_thresh = -bit_cost * combine_cost_factor;
  620. const double curr_cost_diff =
  621. HistogramAddEval(histograms[first], histograms[idx],
  622. cur_combo, bit_cost_thresh);
  623. if (curr_cost_diff < bit_cost_thresh) {
  624. // Try to merge two histograms only if the combo is a trivial one or
  625. // the two candidate histograms are already non-trivial.
  626. // For some images, 'try_combine' turns out to be false for a lot of
  627. // histogram pairs. In that case, we fallback to combining
  628. // histograms as usual to avoid increasing the header size.
  629. const int try_combine =
  630. (cur_combo->trivial_symbol_ != VP8L_NON_TRIVIAL_SYM) ||
  631. ((histograms[idx]->trivial_symbol_ == VP8L_NON_TRIVIAL_SYM) &&
  632. (histograms[first]->trivial_symbol_ == VP8L_NON_TRIVIAL_SYM));
  633. const int max_combine_failures = 32;
  634. if (try_combine ||
  635. bin_info[bin_id].num_combine_failures >= max_combine_failures) {
  636. // move the (better) merged histogram to its final slot
  637. HistogramSwap(&cur_combo, &histograms[first]);
  638. HistogramSetRemoveHistogram(image_histo, idx, num_used);
  639. cluster_mappings[clusters[idx]] = clusters[first];
  640. } else {
  641. ++bin_info[bin_id].num_combine_failures;
  642. }
  643. }
  644. }
  645. }
  646. if (low_effort) {
  647. // for low_effort case, update the final cost when everything is merged
  648. for (idx = 0; idx < image_histo->size; ++idx) {
  649. if (histograms[idx] == NULL) continue;
  650. UpdateHistogramCost(histograms[idx]);
  651. }
  652. }
  653. }
  654. // Implement a Lehmer random number generator with a multiplicative constant of
  655. // 48271 and a modulo constant of 2^31 - 1.
  656. static uint32_t MyRand(uint32_t* const seed) {
  657. *seed = (uint32_t)(((uint64_t)(*seed) * 48271u) % 2147483647u);
  658. assert(*seed > 0);
  659. return *seed;
  660. }
  661. // -----------------------------------------------------------------------------
  662. // Histogram pairs priority queue
  663. // Pair of histograms. Negative idx1 value means that pair is out-of-date.
  664. typedef struct {
  665. int idx1;
  666. int idx2;
  667. double cost_diff;
  668. double cost_combo;
  669. } HistogramPair;
  670. typedef struct {
  671. HistogramPair* queue;
  672. int size;
  673. int max_size;
  674. } HistoQueue;
  675. static int HistoQueueInit(HistoQueue* const histo_queue, const int max_size) {
  676. histo_queue->size = 0;
  677. histo_queue->max_size = max_size;
  678. // We allocate max_size + 1 because the last element at index "size" is
  679. // used as temporary data (and it could be up to max_size).
  680. histo_queue->queue = (HistogramPair*)WebPSafeMalloc(
  681. histo_queue->max_size + 1, sizeof(*histo_queue->queue));
  682. return histo_queue->queue != NULL;
  683. }
  684. static void HistoQueueClear(HistoQueue* const histo_queue) {
  685. assert(histo_queue != NULL);
  686. WebPSafeFree(histo_queue->queue);
  687. histo_queue->size = 0;
  688. histo_queue->max_size = 0;
  689. }
  690. // Pop a specific pair in the queue by replacing it with the last one
  691. // and shrinking the queue.
  692. static void HistoQueuePopPair(HistoQueue* const histo_queue,
  693. HistogramPair* const pair) {
  694. assert(pair >= histo_queue->queue &&
  695. pair < (histo_queue->queue + histo_queue->size));
  696. assert(histo_queue->size > 0);
  697. *pair = histo_queue->queue[histo_queue->size - 1];
  698. --histo_queue->size;
  699. }
  700. // Check whether a pair in the queue should be updated as head or not.
  701. static void HistoQueueUpdateHead(HistoQueue* const histo_queue,
  702. HistogramPair* const pair) {
  703. assert(pair->cost_diff < 0.);
  704. assert(pair >= histo_queue->queue &&
  705. pair < (histo_queue->queue + histo_queue->size));
  706. assert(histo_queue->size > 0);
  707. if (pair->cost_diff < histo_queue->queue[0].cost_diff) {
  708. // Replace the best pair.
  709. const HistogramPair tmp = histo_queue->queue[0];
  710. histo_queue->queue[0] = *pair;
  711. *pair = tmp;
  712. }
  713. }
  714. // Update the cost diff and combo of a pair of histograms. This needs to be
  715. // called when the the histograms have been merged with a third one.
  716. static void HistoQueueUpdatePair(const VP8LHistogram* const h1,
  717. const VP8LHistogram* const h2,
  718. double threshold,
  719. HistogramPair* const pair) {
  720. const double sum_cost = h1->bit_cost_ + h2->bit_cost_;
  721. pair->cost_combo = 0.;
  722. GetCombinedHistogramEntropy(h1, h2, sum_cost + threshold, &pair->cost_combo);
  723. pair->cost_diff = pair->cost_combo - sum_cost;
  724. }
  725. // Create a pair from indices "idx1" and "idx2" provided its cost
  726. // is inferior to "threshold", a negative entropy.
  727. // It returns the cost of the pair, or 0. if it superior to threshold.
  728. static double HistoQueuePush(HistoQueue* const histo_queue,
  729. VP8LHistogram** const histograms, int idx1,
  730. int idx2, double threshold) {
  731. const VP8LHistogram* h1;
  732. const VP8LHistogram* h2;
  733. HistogramPair pair;
  734. // Stop here if the queue is full.
  735. if (histo_queue->size == histo_queue->max_size) return 0.;
  736. assert(threshold <= 0.);
  737. if (idx1 > idx2) {
  738. const int tmp = idx2;
  739. idx2 = idx1;
  740. idx1 = tmp;
  741. }
  742. pair.idx1 = idx1;
  743. pair.idx2 = idx2;
  744. h1 = histograms[idx1];
  745. h2 = histograms[idx2];
  746. HistoQueueUpdatePair(h1, h2, threshold, &pair);
  747. // Do not even consider the pair if it does not improve the entropy.
  748. if (pair.cost_diff >= threshold) return 0.;
  749. histo_queue->queue[histo_queue->size++] = pair;
  750. HistoQueueUpdateHead(histo_queue, &histo_queue->queue[histo_queue->size - 1]);
  751. return pair.cost_diff;
  752. }
  753. // -----------------------------------------------------------------------------
  754. // Combines histograms by continuously choosing the one with the highest cost
  755. // reduction.
  756. static int HistogramCombineGreedy(VP8LHistogramSet* const image_histo,
  757. int* const num_used) {
  758. int ok = 0;
  759. const int image_histo_size = image_histo->size;
  760. int i, j;
  761. VP8LHistogram** const histograms = image_histo->histograms;
  762. // Priority queue of histogram pairs.
  763. HistoQueue histo_queue;
  764. // image_histo_size^2 for the queue size is safe. If you look at
  765. // HistogramCombineGreedy, and imagine that UpdateQueueFront always pushes
  766. // data to the queue, you insert at most:
  767. // - image_histo_size*(image_histo_size-1)/2 (the first two for loops)
  768. // - image_histo_size - 1 in the last for loop at the first iteration of
  769. // the while loop, image_histo_size - 2 at the second iteration ...
  770. // therefore image_histo_size*(image_histo_size-1)/2 overall too
  771. if (!HistoQueueInit(&histo_queue, image_histo_size * image_histo_size)) {
  772. goto End;
  773. }
  774. for (i = 0; i < image_histo_size; ++i) {
  775. if (image_histo->histograms[i] == NULL) continue;
  776. for (j = i + 1; j < image_histo_size; ++j) {
  777. // Initialize queue.
  778. if (image_histo->histograms[j] == NULL) continue;
  779. HistoQueuePush(&histo_queue, histograms, i, j, 0.);
  780. }
  781. }
  782. while (histo_queue.size > 0) {
  783. const int idx1 = histo_queue.queue[0].idx1;
  784. const int idx2 = histo_queue.queue[0].idx2;
  785. HistogramAdd(histograms[idx2], histograms[idx1], histograms[idx1]);
  786. histograms[idx1]->bit_cost_ = histo_queue.queue[0].cost_combo;
  787. // Remove merged histogram.
  788. HistogramSetRemoveHistogram(image_histo, idx2, num_used);
  789. // Remove pairs intersecting the just combined best pair.
  790. for (i = 0; i < histo_queue.size;) {
  791. HistogramPair* const p = histo_queue.queue + i;
  792. if (p->idx1 == idx1 || p->idx2 == idx1 ||
  793. p->idx1 == idx2 || p->idx2 == idx2) {
  794. HistoQueuePopPair(&histo_queue, p);
  795. } else {
  796. HistoQueueUpdateHead(&histo_queue, p);
  797. ++i;
  798. }
  799. }
  800. // Push new pairs formed with combined histogram to the queue.
  801. for (i = 0; i < image_histo->size; ++i) {
  802. if (i == idx1 || image_histo->histograms[i] == NULL) continue;
  803. HistoQueuePush(&histo_queue, image_histo->histograms, idx1, i, 0.);
  804. }
  805. }
  806. ok = 1;
  807. End:
  808. HistoQueueClear(&histo_queue);
  809. return ok;
  810. }
  811. // Perform histogram aggregation using a stochastic approach.
  812. // 'do_greedy' is set to 1 if a greedy approach needs to be performed
  813. // afterwards, 0 otherwise.
  814. static int PairComparison(const void* idx1, const void* idx2) {
  815. // To be used with bsearch: <0 when *idx1<*idx2, >0 if >, 0 when ==.
  816. return (*(int*) idx1 - *(int*) idx2);
  817. }
  818. static int HistogramCombineStochastic(VP8LHistogramSet* const image_histo,
  819. int* const num_used, int min_cluster_size,
  820. int* const do_greedy) {
  821. int j, iter;
  822. uint32_t seed = 1;
  823. int tries_with_no_success = 0;
  824. const int outer_iters = *num_used;
  825. const int num_tries_no_success = outer_iters / 2;
  826. VP8LHistogram** const histograms = image_histo->histograms;
  827. // Priority queue of histogram pairs. Its size of 'kHistoQueueSize'
  828. // impacts the quality of the compression and the speed: the smaller the
  829. // faster but the worse for the compression.
  830. HistoQueue histo_queue;
  831. const int kHistoQueueSize = 9;
  832. int ok = 0;
  833. // mapping from an index in image_histo with no NULL histogram to the full
  834. // blown image_histo.
  835. int* mappings;
  836. if (*num_used < min_cluster_size) {
  837. *do_greedy = 1;
  838. return 1;
  839. }
  840. mappings = (int*) WebPSafeMalloc(*num_used, sizeof(*mappings));
  841. if (mappings == NULL) return 0;
  842. if (!HistoQueueInit(&histo_queue, kHistoQueueSize)) goto End;
  843. // Fill the initial mapping.
  844. for (j = 0, iter = 0; iter < image_histo->size; ++iter) {
  845. if (histograms[iter] == NULL) continue;
  846. mappings[j++] = iter;
  847. }
  848. assert(j == *num_used);
  849. // Collapse similar histograms in 'image_histo'.
  850. for (iter = 0;
  851. iter < outer_iters && *num_used >= min_cluster_size &&
  852. ++tries_with_no_success < num_tries_no_success;
  853. ++iter) {
  854. int* mapping_index;
  855. double best_cost =
  856. (histo_queue.size == 0) ? 0. : histo_queue.queue[0].cost_diff;
  857. int best_idx1 = -1, best_idx2 = 1;
  858. const uint32_t rand_range = (*num_used - 1) * (*num_used);
  859. // (*num_used) / 2 was chosen empirically. Less means faster but worse
  860. // compression.
  861. const int num_tries = (*num_used) / 2;
  862. // Pick random samples.
  863. for (j = 0; *num_used >= 2 && j < num_tries; ++j) {
  864. double curr_cost;
  865. // Choose two different histograms at random and try to combine them.
  866. const uint32_t tmp = MyRand(&seed) % rand_range;
  867. uint32_t idx1 = tmp / (*num_used - 1);
  868. uint32_t idx2 = tmp % (*num_used - 1);
  869. if (idx2 >= idx1) ++idx2;
  870. idx1 = mappings[idx1];
  871. idx2 = mappings[idx2];
  872. // Calculate cost reduction on combination.
  873. curr_cost =
  874. HistoQueuePush(&histo_queue, histograms, idx1, idx2, best_cost);
  875. if (curr_cost < 0) { // found a better pair?
  876. best_cost = curr_cost;
  877. // Empty the queue if we reached full capacity.
  878. if (histo_queue.size == histo_queue.max_size) break;
  879. }
  880. }
  881. if (histo_queue.size == 0) continue;
  882. // Get the best histograms.
  883. best_idx1 = histo_queue.queue[0].idx1;
  884. best_idx2 = histo_queue.queue[0].idx2;
  885. assert(best_idx1 < best_idx2);
  886. // Pop best_idx2 from mappings.
  887. mapping_index = (int*) bsearch(&best_idx2, mappings, *num_used,
  888. sizeof(best_idx2), &PairComparison);
  889. assert(mapping_index != NULL);
  890. memmove(mapping_index, mapping_index + 1, sizeof(*mapping_index) *
  891. ((*num_used) - (mapping_index - mappings) - 1));
  892. // Merge the histograms and remove best_idx2 from the queue.
  893. HistogramAdd(histograms[best_idx2], histograms[best_idx1],
  894. histograms[best_idx1]);
  895. histograms[best_idx1]->bit_cost_ = histo_queue.queue[0].cost_combo;
  896. HistogramSetRemoveHistogram(image_histo, best_idx2, num_used);
  897. // Parse the queue and update each pair that deals with best_idx1,
  898. // best_idx2 or image_histo_size.
  899. for (j = 0; j < histo_queue.size;) {
  900. HistogramPair* const p = histo_queue.queue + j;
  901. const int is_idx1_best = p->idx1 == best_idx1 || p->idx1 == best_idx2;
  902. const int is_idx2_best = p->idx2 == best_idx1 || p->idx2 == best_idx2;
  903. int do_eval = 0;
  904. // The front pair could have been duplicated by a random pick so
  905. // check for it all the time nevertheless.
  906. if (is_idx1_best && is_idx2_best) {
  907. HistoQueuePopPair(&histo_queue, p);
  908. continue;
  909. }
  910. // Any pair containing one of the two best indices should only refer to
  911. // best_idx1. Its cost should also be updated.
  912. if (is_idx1_best) {
  913. p->idx1 = best_idx1;
  914. do_eval = 1;
  915. } else if (is_idx2_best) {
  916. p->idx2 = best_idx1;
  917. do_eval = 1;
  918. }
  919. // Make sure the index order is respected.
  920. if (p->idx1 > p->idx2) {
  921. const int tmp = p->idx2;
  922. p->idx2 = p->idx1;
  923. p->idx1 = tmp;
  924. }
  925. if (do_eval) {
  926. // Re-evaluate the cost of an updated pair.
  927. HistoQueueUpdatePair(histograms[p->idx1], histograms[p->idx2], 0., p);
  928. if (p->cost_diff >= 0.) {
  929. HistoQueuePopPair(&histo_queue, p);
  930. continue;
  931. }
  932. }
  933. HistoQueueUpdateHead(&histo_queue, p);
  934. ++j;
  935. }
  936. tries_with_no_success = 0;
  937. }
  938. *do_greedy = (*num_used <= min_cluster_size);
  939. ok = 1;
  940. End:
  941. HistoQueueClear(&histo_queue);
  942. WebPSafeFree(mappings);
  943. return ok;
  944. }
  945. // -----------------------------------------------------------------------------
  946. // Histogram refinement
  947. // Find the best 'out' histogram for each of the 'in' histograms.
  948. // At call-time, 'out' contains the histograms of the clusters.
  949. // Note: we assume that out[]->bit_cost_ is already up-to-date.
  950. static void HistogramRemap(const VP8LHistogramSet* const in,
  951. VP8LHistogramSet* const out,
  952. uint16_t* const symbols) {
  953. int i;
  954. VP8LHistogram** const in_histo = in->histograms;
  955. VP8LHistogram** const out_histo = out->histograms;
  956. const int in_size = out->max_size;
  957. const int out_size = out->size;
  958. if (out_size > 1) {
  959. for (i = 0; i < in_size; ++i) {
  960. int best_out = 0;
  961. double best_bits = MAX_COST;
  962. int k;
  963. if (in_histo[i] == NULL) {
  964. // Arbitrarily set to the previous value if unused to help future LZ77.
  965. symbols[i] = symbols[i - 1];
  966. continue;
  967. }
  968. for (k = 0; k < out_size; ++k) {
  969. double cur_bits;
  970. cur_bits = HistogramAddThresh(out_histo[k], in_histo[i], best_bits);
  971. if (k == 0 || cur_bits < best_bits) {
  972. best_bits = cur_bits;
  973. best_out = k;
  974. }
  975. }
  976. symbols[i] = best_out;
  977. }
  978. } else {
  979. assert(out_size == 1);
  980. for (i = 0; i < in_size; ++i) {
  981. symbols[i] = 0;
  982. }
  983. }
  984. // Recompute each out based on raw and symbols.
  985. VP8LHistogramSetClear(out);
  986. out->size = out_size;
  987. for (i = 0; i < in_size; ++i) {
  988. int idx;
  989. if (in_histo[i] == NULL) continue;
  990. idx = symbols[i];
  991. HistogramAdd(in_histo[i], out_histo[idx], out_histo[idx]);
  992. }
  993. }
  994. static double GetCombineCostFactor(int histo_size, int quality) {
  995. double combine_cost_factor = 0.16;
  996. if (quality < 90) {
  997. if (histo_size > 256) combine_cost_factor /= 2.;
  998. if (histo_size > 512) combine_cost_factor /= 2.;
  999. if (histo_size > 1024) combine_cost_factor /= 2.;
  1000. if (quality <= 50) combine_cost_factor /= 2.;
  1001. }
  1002. return combine_cost_factor;
  1003. }
  1004. // Given a HistogramSet 'set', the mapping of clusters 'cluster_mapping' and the
  1005. // current assignment of the cells in 'symbols', merge the clusters and
  1006. // assign the smallest possible clusters values.
  1007. static void OptimizeHistogramSymbols(const VP8LHistogramSet* const set,
  1008. uint16_t* const cluster_mappings,
  1009. int num_clusters,
  1010. uint16_t* const cluster_mappings_tmp,
  1011. uint16_t* const symbols) {
  1012. int i, cluster_max;
  1013. int do_continue = 1;
  1014. // First, assign the lowest cluster to each pixel.
  1015. while (do_continue) {
  1016. do_continue = 0;
  1017. for (i = 0; i < num_clusters; ++i) {
  1018. int k;
  1019. k = cluster_mappings[i];
  1020. while (k != cluster_mappings[k]) {
  1021. cluster_mappings[k] = cluster_mappings[cluster_mappings[k]];
  1022. k = cluster_mappings[k];
  1023. }
  1024. if (k != cluster_mappings[i]) {
  1025. do_continue = 1;
  1026. cluster_mappings[i] = k;
  1027. }
  1028. }
  1029. }
  1030. // Create a mapping from a cluster id to its minimal version.
  1031. cluster_max = 0;
  1032. memset(cluster_mappings_tmp, 0,
  1033. set->max_size * sizeof(*cluster_mappings_tmp));
  1034. assert(cluster_mappings[0] == 0);
  1035. // Re-map the ids.
  1036. for (i = 0; i < set->max_size; ++i) {
  1037. int cluster;
  1038. if (symbols[i] == kInvalidHistogramSymbol) continue;
  1039. cluster = cluster_mappings[symbols[i]];
  1040. assert(symbols[i] < num_clusters);
  1041. if (cluster > 0 && cluster_mappings_tmp[cluster] == 0) {
  1042. ++cluster_max;
  1043. cluster_mappings_tmp[cluster] = cluster_max;
  1044. }
  1045. symbols[i] = cluster_mappings_tmp[cluster];
  1046. }
  1047. // Make sure all cluster values are used.
  1048. cluster_max = 0;
  1049. for (i = 0; i < set->max_size; ++i) {
  1050. if (symbols[i] == kInvalidHistogramSymbol) continue;
  1051. if (symbols[i] <= cluster_max) continue;
  1052. ++cluster_max;
  1053. assert(symbols[i] == cluster_max);
  1054. }
  1055. }
  1056. static void RemoveEmptyHistograms(VP8LHistogramSet* const image_histo) {
  1057. uint32_t size;
  1058. int i;
  1059. for (i = 0, size = 0; i < image_histo->size; ++i) {
  1060. if (image_histo->histograms[i] == NULL) continue;
  1061. image_histo->histograms[size++] = image_histo->histograms[i];
  1062. }
  1063. image_histo->size = size;
  1064. }
  1065. int VP8LGetHistoImageSymbols(int xsize, int ysize,
  1066. const VP8LBackwardRefs* const refs,
  1067. int quality, int low_effort,
  1068. int histogram_bits, int cache_bits,
  1069. VP8LHistogramSet* const image_histo,
  1070. VP8LHistogram* const tmp_histo,
  1071. uint16_t* const histogram_symbols) {
  1072. int ok = 0;
  1073. const int histo_xsize =
  1074. histogram_bits ? VP8LSubSampleSize(xsize, histogram_bits) : 1;
  1075. const int histo_ysize =
  1076. histogram_bits ? VP8LSubSampleSize(ysize, histogram_bits) : 1;
  1077. const int image_histo_raw_size = histo_xsize * histo_ysize;
  1078. VP8LHistogramSet* const orig_histo =
  1079. VP8LAllocateHistogramSet(image_histo_raw_size, cache_bits);
  1080. // Don't attempt linear bin-partition heuristic for
  1081. // histograms of small sizes (as bin_map will be very sparse) and
  1082. // maximum quality q==100 (to preserve the compression gains at that level).
  1083. const int entropy_combine_num_bins = low_effort ? NUM_PARTITIONS : BIN_SIZE;
  1084. int entropy_combine;
  1085. uint16_t* const map_tmp =
  1086. WebPSafeMalloc(2 * image_histo_raw_size, sizeof(map_tmp));
  1087. uint16_t* const cluster_mappings = map_tmp + image_histo_raw_size;
  1088. int num_used = image_histo_raw_size;
  1089. if (orig_histo == NULL || map_tmp == NULL) goto Error;
  1090. // Construct the histograms from backward references.
  1091. HistogramBuild(xsize, histogram_bits, refs, orig_histo);
  1092. // Copies the histograms and computes its bit_cost.
  1093. // histogram_symbols is optimized
  1094. HistogramCopyAndAnalyze(orig_histo, image_histo, &num_used,
  1095. histogram_symbols);
  1096. entropy_combine =
  1097. (num_used > entropy_combine_num_bins * 2) && (quality < 100);
  1098. if (entropy_combine) {
  1099. uint16_t* const bin_map = map_tmp;
  1100. const double combine_cost_factor =
  1101. GetCombineCostFactor(image_histo_raw_size, quality);
  1102. const uint32_t num_clusters = num_used;
  1103. HistogramAnalyzeEntropyBin(image_histo, bin_map, low_effort);
  1104. // Collapse histograms with similar entropy.
  1105. HistogramCombineEntropyBin(image_histo, &num_used, histogram_symbols,
  1106. cluster_mappings, tmp_histo, bin_map,
  1107. entropy_combine_num_bins, combine_cost_factor,
  1108. low_effort);
  1109. OptimizeHistogramSymbols(image_histo, cluster_mappings, num_clusters,
  1110. map_tmp, histogram_symbols);
  1111. }
  1112. // Don't combine the histograms using stochastic and greedy heuristics for
  1113. // low-effort compression mode.
  1114. if (!low_effort || !entropy_combine) {
  1115. const float x = quality / 100.f;
  1116. // cubic ramp between 1 and MAX_HISTO_GREEDY:
  1117. const int threshold_size = (int)(1 + (x * x * x) * (MAX_HISTO_GREEDY - 1));
  1118. int do_greedy;
  1119. if (!HistogramCombineStochastic(image_histo, &num_used, threshold_size,
  1120. &do_greedy)) {
  1121. goto Error;
  1122. }
  1123. if (do_greedy) {
  1124. RemoveEmptyHistograms(image_histo);
  1125. if (!HistogramCombineGreedy(image_histo, &num_used)) {
  1126. goto Error;
  1127. }
  1128. }
  1129. }
  1130. // Find the optimal map from original histograms to the final ones.
  1131. RemoveEmptyHistograms(image_histo);
  1132. HistogramRemap(orig_histo, image_histo, histogram_symbols);
  1133. ok = 1;
  1134. Error:
  1135. VP8LFreeHistogramSet(orig_histo);
  1136. WebPSafeFree(map_tmp);
  1137. return ok;
  1138. }