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// Image transforms and color space conversion methods for lossless decoder.
11//
12// Authors: Vikas Arora (vikaas.arora@gmail.com)
13//          Jyrki Alakuijala (jyrki@google.com)
14//          Urvang Joshi (urvang@google.com)
15
16#include "./dsp.h"
17
18// Define the following if target arch is sure to have SSE2
19// #define WEBP_TARGET_HAS_SSE2
20
21#if defined(__cplusplus) || defined(c_plusplus)
22extern "C" {
23#endif
24
25#if defined(WEBP_TARGET_HAS_SSE2)
26#include <emmintrin.h>
27#endif
28
29#include <math.h>
30#include <stdlib.h>
31#include "./lossless.h"
32#include "../dec/vp8li.h"
33#include "./yuv.h"
34
35#define MAX_DIFF_COST (1e30f)
36
37// lookup table for small values of log2(int)
38#define APPROX_LOG_MAX  4096
39#define LOG_2_RECIPROCAL 1.44269504088896338700465094007086
40const float kLog2Table[LOG_LOOKUP_IDX_MAX] = {
41  0.0000000000000000f, 0.0000000000000000f,
42  1.0000000000000000f, 1.5849625007211560f,
43  2.0000000000000000f, 2.3219280948873621f,
44  2.5849625007211560f, 2.8073549220576041f,
45  3.0000000000000000f, 3.1699250014423121f,
46  3.3219280948873621f, 3.4594316186372973f,
47  3.5849625007211560f, 3.7004397181410921f,
48  3.8073549220576041f, 3.9068905956085187f,
49  4.0000000000000000f, 4.0874628412503390f,
50  4.1699250014423121f, 4.2479275134435852f,
51  4.3219280948873626f, 4.3923174227787606f,
52  4.4594316186372973f, 4.5235619560570130f,
53  4.5849625007211560f, 4.6438561897747243f,
54  4.7004397181410917f, 4.7548875021634682f,
55  4.8073549220576037f, 4.8579809951275718f,
56  4.9068905956085187f, 4.9541963103868749f,
57  5.0000000000000000f, 5.0443941193584533f,
58  5.0874628412503390f, 5.1292830169449663f,
59  5.1699250014423121f, 5.2094533656289501f,
60  5.2479275134435852f, 5.2854022188622487f,
61  5.3219280948873626f, 5.3575520046180837f,
62  5.3923174227787606f, 5.4262647547020979f,
63  5.4594316186372973f, 5.4918530963296747f,
64  5.5235619560570130f, 5.5545888516776376f,
65  5.5849625007211560f, 5.6147098441152083f,
66  5.6438561897747243f, 5.6724253419714951f,
67  5.7004397181410917f, 5.7279204545631987f,
68  5.7548875021634682f, 5.7813597135246599f,
69  5.8073549220576037f, 5.8328900141647412f,
70  5.8579809951275718f, 5.8826430493618415f,
71  5.9068905956085187f, 5.9307373375628866f,
72  5.9541963103868749f, 5.9772799234999167f,
73  6.0000000000000000f, 6.0223678130284543f,
74  6.0443941193584533f, 6.0660891904577720f,
75  6.0874628412503390f, 6.1085244567781691f,
76  6.1292830169449663f, 6.1497471195046822f,
77  6.1699250014423121f, 6.1898245588800175f,
78  6.2094533656289501f, 6.2288186904958804f,
79  6.2479275134435852f, 6.2667865406949010f,
80  6.2854022188622487f, 6.3037807481771030f,
81  6.3219280948873626f, 6.3398500028846243f,
82  6.3575520046180837f, 6.3750394313469245f,
83  6.3923174227787606f, 6.4093909361377017f,
84  6.4262647547020979f, 6.4429434958487279f,
85  6.4594316186372973f, 6.4757334309663976f,
86  6.4918530963296747f, 6.5077946401986963f,
87  6.5235619560570130f, 6.5391588111080309f,
88  6.5545888516776376f, 6.5698556083309478f,
89  6.5849625007211560f, 6.5999128421871278f,
90  6.6147098441152083f, 6.6293566200796094f,
91  6.6438561897747243f, 6.6582114827517946f,
92  6.6724253419714951f, 6.6865005271832185f,
93  6.7004397181410917f, 6.7142455176661224f,
94  6.7279204545631987f, 6.7414669864011464f,
95  6.7548875021634682f, 6.7681843247769259f,
96  6.7813597135246599f, 6.7944158663501061f,
97  6.8073549220576037f, 6.8201789624151878f,
98  6.8328900141647412f, 6.8454900509443747f,
99  6.8579809951275718f, 6.8703647195834047f,
100  6.8826430493618415f, 6.8948177633079437f,
101  6.9068905956085187f, 6.9188632372745946f,
102  6.9307373375628866f, 6.9425145053392398f,
103  6.9541963103868749f, 6.9657842846620869f,
104  6.9772799234999167f, 6.9886846867721654f,
105  7.0000000000000000f, 7.0112272554232539f,
106  7.0223678130284543f, 7.0334230015374501f,
107  7.0443941193584533f, 7.0552824355011898f,
108  7.0660891904577720f, 7.0768155970508308f,
109  7.0874628412503390f, 7.0980320829605263f,
110  7.1085244567781691f, 7.1189410727235076f,
111  7.1292830169449663f, 7.1395513523987936f,
112  7.1497471195046822f, 7.1598713367783890f,
113  7.1699250014423121f, 7.1799090900149344f,
114  7.1898245588800175f, 7.1996723448363644f,
115  7.2094533656289501f, 7.2191685204621611f,
116  7.2288186904958804f, 7.2384047393250785f,
117  7.2479275134435852f, 7.2573878426926521f,
118  7.2667865406949010f, 7.2761244052742375f,
119  7.2854022188622487f, 7.2946207488916270f,
120  7.3037807481771030f, 7.3128829552843557f,
121  7.3219280948873626f, 7.3309168781146167f,
122  7.3398500028846243f, 7.3487281542310771f,
123  7.3575520046180837f, 7.3663222142458160f,
124  7.3750394313469245f, 7.3837042924740519f,
125  7.3923174227787606f, 7.4008794362821843f,
126  7.4093909361377017f, 7.4178525148858982f,
127  7.4262647547020979f, 7.4346282276367245f,
128  7.4429434958487279f, 7.4512111118323289f,
129  7.4594316186372973f, 7.4676055500829976f,
130  7.4757334309663976f, 7.4838157772642563f,
131  7.4918530963296747f, 7.4998458870832056f,
132  7.5077946401986963f, 7.5156998382840427f,
133  7.5235619560570130f, 7.5313814605163118f,
134  7.5391588111080309f, 7.5468944598876364f,
135  7.5545888516776376f, 7.5622424242210728f,
136  7.5698556083309478f, 7.5774288280357486f,
137  7.5849625007211560f, 7.5924570372680806f,
138  7.5999128421871278f, 7.6073303137496104f,
139  7.6147098441152083f, 7.6220518194563764f,
140  7.6293566200796094f, 7.6366246205436487f,
141  7.6438561897747243f, 7.6510516911789281f,
142  7.6582114827517946f, 7.6653359171851764f,
143  7.6724253419714951f, 7.6794800995054464f,
144  7.6865005271832185f, 7.6934869574993252f,
145  7.7004397181410917f, 7.7073591320808825f,
146  7.7142455176661224f, 7.7210991887071855f,
147  7.7279204545631987f, 7.7347096202258383f,
148  7.7414669864011464f, 7.7481928495894605f,
149  7.7548875021634682f, 7.7615512324444795f,
150  7.7681843247769259f, 7.7747870596011736f,
151  7.7813597135246599f, 7.7879025593914317f,
152  7.7944158663501061f, 7.8008998999203047f,
153  7.8073549220576037f, 7.8137811912170374f,
154  7.8201789624151878f, 7.8265484872909150f,
155  7.8328900141647412f, 7.8392037880969436f,
156  7.8454900509443747f, 7.8517490414160571f,
157  7.8579809951275718f, 7.8641861446542797f,
158  7.8703647195834047f, 7.8765169465649993f,
159  7.8826430493618415f, 7.8887432488982591f,
160  7.8948177633079437f, 7.9008668079807486f,
161  7.9068905956085187f, 7.9128893362299619f,
162  7.9188632372745946f, 7.9248125036057812f,
163  7.9307373375628866f, 7.9366379390025709f,
164  7.9425145053392398f, 7.9483672315846778f,
165  7.9541963103868749f, 7.9600019320680805f,
166  7.9657842846620869f, 7.9715435539507719f,
167  7.9772799234999167f, 7.9829935746943103f,
168  7.9886846867721654f, 7.9943534368588577f
169};
170
171const float kSLog2Table[LOG_LOOKUP_IDX_MAX] = {
172  0.00000000f,    0.00000000f,  2.00000000f,   4.75488750f,
173  8.00000000f,   11.60964047f,  15.50977500f,  19.65148445f,
174  24.00000000f,  28.52932501f,  33.21928095f,  38.05374781f,
175  43.01955001f,  48.10571634f,  53.30296891f,  58.60335893f,
176  64.00000000f,  69.48686830f,  75.05865003f,  80.71062276f,
177  86.43856190f,  92.23866588f,  98.10749561f,  104.04192499f,
178  110.03910002f, 116.09640474f, 122.21143267f, 128.38196256f,
179  134.60593782f, 140.88144886f, 147.20671787f, 153.58008562f,
180  160.00000000f, 166.46500594f, 172.97373660f, 179.52490559f,
181  186.11730005f, 192.74977453f, 199.42124551f, 206.13068654f,
182  212.87712380f, 219.65963219f, 226.47733176f, 233.32938445f,
183  240.21499122f, 247.13338933f, 254.08384998f, 261.06567603f,
184  268.07820003f, 275.12078236f, 282.19280949f, 289.29369244f,
185  296.42286534f, 303.57978409f, 310.76392512f, 317.97478424f,
186  325.21187564f, 332.47473081f, 339.76289772f, 347.07593991f,
187  354.41343574f, 361.77497759f, 369.16017124f, 376.56863518f,
188  384.00000000f, 391.45390785f, 398.93001188f, 406.42797576f,
189  413.94747321f, 421.48818752f, 429.04981119f, 436.63204548f,
190  444.23460010f, 451.85719280f, 459.49954906f, 467.16140179f,
191  474.84249102f, 482.54256363f, 490.26137307f, 497.99867911f,
192  505.75424759f, 513.52785023f, 521.31926438f, 529.12827280f,
193  536.95466351f, 544.79822957f, 552.65876890f, 560.53608414f,
194  568.42998244f, 576.34027536f, 584.26677867f, 592.20931226f,
195  600.16769996f, 608.14176943f, 616.13135206f, 624.13628279f,
196  632.15640007f, 640.19154569f, 648.24156472f, 656.30630539f,
197  664.38561898f, 672.47935976f, 680.58738488f, 688.70955430f,
198  696.84573069f, 704.99577935f, 713.15956818f, 721.33696754f,
199  729.52785023f, 737.73209140f, 745.94956849f, 754.18016116f,
200  762.42375127f, 770.68022275f, 778.94946161f, 787.23135586f,
201  795.52579543f, 803.83267219f, 812.15187982f, 820.48331383f,
202  828.82687147f, 837.18245171f, 845.54995518f, 853.92928416f,
203  862.32034249f, 870.72303558f, 879.13727036f, 887.56295522f,
204  896.00000000f, 904.44831595f, 912.90781569f, 921.37841320f,
205  929.86002376f, 938.35256392f, 946.85595152f, 955.37010560f,
206  963.89494641f, 972.43039537f, 980.97637504f, 989.53280911f,
207  998.09962237f, 1006.67674069f, 1015.26409097f, 1023.86160116f,
208  1032.46920021f, 1041.08681805f, 1049.71438560f, 1058.35183469f,
209  1066.99909811f, 1075.65610955f, 1084.32280357f, 1092.99911564f,
210  1101.68498204f, 1110.38033993f, 1119.08512727f, 1127.79928282f,
211  1136.52274614f, 1145.25545758f, 1153.99735821f, 1162.74838989f,
212  1171.50849518f, 1180.27761738f, 1189.05570047f, 1197.84268914f,
213  1206.63852876f, 1215.44316535f, 1224.25654560f, 1233.07861684f,
214  1241.90932703f, 1250.74862473f, 1259.59645914f, 1268.45278005f,
215  1277.31753781f, 1286.19068338f, 1295.07216828f, 1303.96194457f,
216  1312.85996488f, 1321.76618236f, 1330.68055071f, 1339.60302413f,
217  1348.53355734f, 1357.47210556f, 1366.41862452f, 1375.37307041f,
218  1384.33539991f, 1393.30557020f, 1402.28353887f, 1411.26926400f,
219  1420.26270412f, 1429.26381818f, 1438.27256558f, 1447.28890615f,
220  1456.31280014f, 1465.34420819f, 1474.38309138f, 1483.42941118f,
221  1492.48312945f, 1501.54420843f, 1510.61261078f, 1519.68829949f,
222  1528.77123795f, 1537.86138993f, 1546.95871952f, 1556.06319119f,
223  1565.17476976f, 1574.29342040f, 1583.41910860f, 1592.55180020f,
224  1601.69146137f, 1610.83805860f, 1619.99155871f, 1629.15192882f,
225  1638.31913637f, 1647.49314911f, 1656.67393509f, 1665.86146266f,
226  1675.05570047f, 1684.25661744f, 1693.46418280f, 1702.67836605f,
227  1711.89913698f, 1721.12646563f, 1730.36032233f, 1739.60067768f,
228  1748.84750254f, 1758.10076802f, 1767.36044551f, 1776.62650662f,
229  1785.89892323f, 1795.17766747f, 1804.46271172f, 1813.75402857f,
230  1823.05159087f, 1832.35537170f, 1841.66534438f, 1850.98148244f,
231  1860.30375965f, 1869.63214999f, 1878.96662767f, 1888.30716711f,
232  1897.65374295f, 1907.00633003f, 1916.36490342f, 1925.72943838f,
233  1935.09991037f, 1944.47629506f, 1953.85856831f, 1963.24670620f,
234  1972.64068498f, 1982.04048108f, 1991.44607117f, 2000.85743204f,
235  2010.27454072f, 2019.69737440f, 2029.12591044f, 2038.56012640f
236};
237
238float VP8LFastSLog2Slow(int v) {
239  assert(v >= LOG_LOOKUP_IDX_MAX);
240  if (v < APPROX_LOG_MAX) {
241    int log_cnt = 0;
242    const float v_f = (float)v;
243    while (v >= LOG_LOOKUP_IDX_MAX) {
244      ++log_cnt;
245      v = v >> 1;
246    }
247    return v_f * (kLog2Table[v] + log_cnt);
248  } else {
249    return (float)(LOG_2_RECIPROCAL * v * log((double)v));
250  }
251}
252
253float VP8LFastLog2Slow(int v) {
254  assert(v >= LOG_LOOKUP_IDX_MAX);
255  if (v < APPROX_LOG_MAX) {
256    int log_cnt = 0;
257    while (v >= LOG_LOOKUP_IDX_MAX) {
258      ++log_cnt;
259      v = v >> 1;
260    }
261    return kLog2Table[v] + log_cnt;
262  } else {
263    return (float)(LOG_2_RECIPROCAL * log((double)v));
264  }
265}
266
267//------------------------------------------------------------------------------
268// Image transforms.
269
270// In-place sum of each component with mod 256.
271static WEBP_INLINE void AddPixelsEq(uint32_t* a, uint32_t b) {
272  const uint32_t alpha_and_green = (*a & 0xff00ff00u) + (b & 0xff00ff00u);
273  const uint32_t red_and_blue = (*a & 0x00ff00ffu) + (b & 0x00ff00ffu);
274  *a = (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu);
275}
276
277static WEBP_INLINE uint32_t Average2(uint32_t a0, uint32_t a1) {
278  return (((a0 ^ a1) & 0xfefefefeL) >> 1) + (a0 & a1);
279}
280
281static WEBP_INLINE uint32_t Average3(uint32_t a0, uint32_t a1, uint32_t a2) {
282  return Average2(Average2(a0, a2), a1);
283}
284
285static WEBP_INLINE uint32_t Average4(uint32_t a0, uint32_t a1,
286                                     uint32_t a2, uint32_t a3) {
287  return Average2(Average2(a0, a1), Average2(a2, a3));
288}
289
290#if defined(WEBP_TARGET_HAS_SSE2)
291static WEBP_INLINE uint32_t ClampedAddSubtractFull(uint32_t c0, uint32_t c1,
292                                                   uint32_t c2) {
293  const __m128i zero = _mm_setzero_si128();
294  const __m128i C0 = _mm_unpacklo_epi8(_mm_cvtsi32_si128(c0), zero);
295  const __m128i C1 = _mm_unpacklo_epi8(_mm_cvtsi32_si128(c1), zero);
296  const __m128i C2 = _mm_unpacklo_epi8(_mm_cvtsi32_si128(c2), zero);
297  const __m128i V1 = _mm_add_epi16(C0, C1);
298  const __m128i V2 = _mm_sub_epi16(V1, C2);
299  const __m128i b = _mm_packus_epi16(V2, V2);
300  const uint32_t output = _mm_cvtsi128_si32(b);
301  return output;
302}
303
304static WEBP_INLINE uint32_t ClampedAddSubtractHalf(uint32_t c0, uint32_t c1,
305                                                   uint32_t c2) {
306  const uint32_t ave = Average2(c0, c1);
307  const __m128i zero = _mm_setzero_si128();
308  const __m128i A0 = _mm_unpacklo_epi8(_mm_cvtsi32_si128(ave), zero);
309  const __m128i B0 = _mm_unpacklo_epi8(_mm_cvtsi32_si128(c2), zero);
310  const __m128i A1 = _mm_sub_epi16(A0, B0);
311  const __m128i BgtA = _mm_cmpgt_epi16(B0, A0);
312  const __m128i A2 = _mm_sub_epi16(A1, BgtA);
313  const __m128i A3 = _mm_srai_epi16(A2, 1);
314  const __m128i A4 = _mm_add_epi16(A0, A3);
315  const __m128i A5 = _mm_packus_epi16(A4, A4);
316  const uint32_t output = _mm_cvtsi128_si32(A5);
317  return output;
318}
319
320static WEBP_INLINE uint32_t Select(uint32_t a, uint32_t b, uint32_t c) {
321  int pa_minus_pb;
322  const __m128i zero = _mm_setzero_si128();
323  const __m128i A0 = _mm_cvtsi32_si128(a);
324  const __m128i B0 = _mm_cvtsi32_si128(b);
325  const __m128i C0 = _mm_cvtsi32_si128(c);
326  const __m128i AC0 = _mm_subs_epu8(A0, C0);
327  const __m128i CA0 = _mm_subs_epu8(C0, A0);
328  const __m128i BC0 = _mm_subs_epu8(B0, C0);
329  const __m128i CB0 = _mm_subs_epu8(C0, B0);
330  const __m128i AC = _mm_or_si128(AC0, CA0);
331  const __m128i BC = _mm_or_si128(BC0, CB0);
332  const __m128i pa = _mm_unpacklo_epi8(AC, zero);  // |a - c|
333  const __m128i pb = _mm_unpacklo_epi8(BC, zero);  // |b - c|
334  const __m128i diff = _mm_sub_epi16(pb, pa);
335  {
336    int16_t out[8];
337    _mm_storeu_si128((__m128i*)out, diff);
338    pa_minus_pb = out[0] + out[1] + out[2] + out[3];
339  }
340  return (pa_minus_pb <= 0) ? a : b;
341}
342
343#else
344
345static WEBP_INLINE uint32_t Clip255(uint32_t a) {
346  if (a < 256) {
347    return a;
348  }
349  // return 0, when a is a negative integer.
350  // return 255, when a is positive.
351  return ~a >> 24;
352}
353
354static WEBP_INLINE int AddSubtractComponentFull(int a, int b, int c) {
355  return Clip255(a + b - c);
356}
357
358static WEBP_INLINE uint32_t ClampedAddSubtractFull(uint32_t c0, uint32_t c1,
359                                                   uint32_t c2) {
360  const int a = AddSubtractComponentFull(c0 >> 24, c1 >> 24, c2 >> 24);
361  const int r = AddSubtractComponentFull((c0 >> 16) & 0xff,
362                                         (c1 >> 16) & 0xff,
363                                         (c2 >> 16) & 0xff);
364  const int g = AddSubtractComponentFull((c0 >> 8) & 0xff,
365                                         (c1 >> 8) & 0xff,
366                                         (c2 >> 8) & 0xff);
367  const int b = AddSubtractComponentFull(c0 & 0xff, c1 & 0xff, c2 & 0xff);
368  return (a << 24) | (r << 16) | (g << 8) | b;
369}
370
371static WEBP_INLINE int AddSubtractComponentHalf(int a, int b) {
372  return Clip255(a + (a - b) / 2);
373}
374
375static WEBP_INLINE uint32_t ClampedAddSubtractHalf(uint32_t c0, uint32_t c1,
376                                                   uint32_t c2) {
377  const uint32_t ave = Average2(c0, c1);
378  const int a = AddSubtractComponentHalf(ave >> 24, c2 >> 24);
379  const int r = AddSubtractComponentHalf((ave >> 16) & 0xff, (c2 >> 16) & 0xff);
380  const int g = AddSubtractComponentHalf((ave >> 8) & 0xff, (c2 >> 8) & 0xff);
381  const int b = AddSubtractComponentHalf((ave >> 0) & 0xff, (c2 >> 0) & 0xff);
382  return (a << 24) | (r << 16) | (g << 8) | b;
383}
384
385static WEBP_INLINE int Sub3(int a, int b, int c) {
386  const int pb = b - c;
387  const int pa = a - c;
388  return abs(pb) - abs(pa);
389}
390
391static WEBP_INLINE uint32_t Select(uint32_t a, uint32_t b, uint32_t c) {
392  const int pa_minus_pb =
393      Sub3((a >> 24)       , (b >> 24)       , (c >> 24)       ) +
394      Sub3((a >> 16) & 0xff, (b >> 16) & 0xff, (c >> 16) & 0xff) +
395      Sub3((a >>  8) & 0xff, (b >>  8) & 0xff, (c >>  8) & 0xff) +
396      Sub3((a      ) & 0xff, (b      ) & 0xff, (c      ) & 0xff);
397  return (pa_minus_pb <= 0) ? a : b;
398}
399#endif
400
401//------------------------------------------------------------------------------
402// Predictors
403
404static uint32_t Predictor0(uint32_t left, const uint32_t* const top) {
405  (void)top;
406  (void)left;
407  return ARGB_BLACK;
408}
409static uint32_t Predictor1(uint32_t left, const uint32_t* const top) {
410  (void)top;
411  return left;
412}
413static uint32_t Predictor2(uint32_t left, const uint32_t* const top) {
414  (void)left;
415  return top[0];
416}
417static uint32_t Predictor3(uint32_t left, const uint32_t* const top) {
418  (void)left;
419  return top[1];
420}
421static uint32_t Predictor4(uint32_t left, const uint32_t* const top) {
422  (void)left;
423  return top[-1];
424}
425static uint32_t Predictor5(uint32_t left, const uint32_t* const top) {
426  const uint32_t pred = Average3(left, top[0], top[1]);
427  return pred;
428}
429static uint32_t Predictor6(uint32_t left, const uint32_t* const top) {
430  const uint32_t pred = Average2(left, top[-1]);
431  return pred;
432}
433static uint32_t Predictor7(uint32_t left, const uint32_t* const top) {
434  const uint32_t pred = Average2(left, top[0]);
435  return pred;
436}
437static uint32_t Predictor8(uint32_t left, const uint32_t* const top) {
438  const uint32_t pred = Average2(top[-1], top[0]);
439  (void)left;
440  return pred;
441}
442static uint32_t Predictor9(uint32_t left, const uint32_t* const top) {
443  const uint32_t pred = Average2(top[0], top[1]);
444  (void)left;
445  return pred;
446}
447static uint32_t Predictor10(uint32_t left, const uint32_t* const top) {
448  const uint32_t pred = Average4(left, top[-1], top[0], top[1]);
449  return pred;
450}
451static uint32_t Predictor11(uint32_t left, const uint32_t* const top) {
452  const uint32_t pred = Select(top[0], left, top[-1]);
453  return pred;
454}
455static uint32_t Predictor12(uint32_t left, const uint32_t* const top) {
456  const uint32_t pred = ClampedAddSubtractFull(left, top[0], top[-1]);
457  return pred;
458}
459static uint32_t Predictor13(uint32_t left, const uint32_t* const top) {
460  const uint32_t pred = ClampedAddSubtractHalf(left, top[0], top[-1]);
461  return pred;
462}
463
464typedef uint32_t (*PredictorFunc)(uint32_t left, const uint32_t* const top);
465static const PredictorFunc kPredictors[16] = {
466  Predictor0, Predictor1, Predictor2, Predictor3,
467  Predictor4, Predictor5, Predictor6, Predictor7,
468  Predictor8, Predictor9, Predictor10, Predictor11,
469  Predictor12, Predictor13,
470  Predictor0, Predictor0    // <- padding security sentinels
471};
472
473// TODO(vikasa): Replace 256 etc with defines.
474static float PredictionCostSpatial(const int* counts,
475                                   int weight_0, double exp_val) {
476  const int significant_symbols = 16;
477  const double exp_decay_factor = 0.6;
478  double bits = weight_0 * counts[0];
479  int i;
480  for (i = 1; i < significant_symbols; ++i) {
481    bits += exp_val * (counts[i] + counts[256 - i]);
482    exp_val *= exp_decay_factor;
483  }
484  return (float)(-0.1 * bits);
485}
486
487// Compute the combined Shanon's entropy for distribution {X} and {X+Y}
488static float CombinedShannonEntropy(const int* const X,
489                                    const int* const Y, int n) {
490  int i;
491  double retval = 0.;
492  int sumX = 0, sumXY = 0;
493  for (i = 0; i < n; ++i) {
494    const int x = X[i];
495    const int xy = X[i] + Y[i];
496    if (x != 0) {
497      sumX += x;
498      retval -= VP8LFastSLog2(x);
499    }
500    if (xy != 0) {
501      sumXY += xy;
502      retval -= VP8LFastSLog2(xy);
503    }
504  }
505  retval += VP8LFastSLog2(sumX) + VP8LFastSLog2(sumXY);
506  return (float)retval;
507}
508
509static float PredictionCostSpatialHistogram(int accumulated[4][256],
510                                            int tile[4][256]) {
511  int i;
512  double retval = 0;
513  for (i = 0; i < 4; ++i) {
514    const double kExpValue = 0.94;
515    retval += PredictionCostSpatial(tile[i], 1, kExpValue);
516    retval += CombinedShannonEntropy(tile[i], accumulated[i], 256);
517  }
518  return (float)retval;
519}
520
521static int GetBestPredictorForTile(int width, int height,
522                                   int tile_x, int tile_y, int bits,
523                                   int accumulated[4][256],
524                                   const uint32_t* const argb_scratch) {
525  const int kNumPredModes = 14;
526  const int col_start = tile_x << bits;
527  const int row_start = tile_y << bits;
528  const int tile_size = 1 << bits;
529  const int ymax = (tile_size <= height - row_start) ?
530      tile_size : height - row_start;
531  const int xmax = (tile_size <= width - col_start) ?
532      tile_size : width - col_start;
533  int histo[4][256];
534  float best_diff = MAX_DIFF_COST;
535  int best_mode = 0;
536
537  int mode;
538  for (mode = 0; mode < kNumPredModes; ++mode) {
539    const uint32_t* current_row = argb_scratch;
540    const PredictorFunc pred_func = kPredictors[mode];
541    float cur_diff;
542    int y;
543    memset(&histo[0][0], 0, sizeof(histo));
544    for (y = 0; y < ymax; ++y) {
545      int x;
546      const int row = row_start + y;
547      const uint32_t* const upper_row = current_row;
548      current_row = upper_row + width;
549      for (x = 0; x < xmax; ++x) {
550        const int col = col_start + x;
551        uint32_t predict;
552        uint32_t predict_diff;
553        if (row == 0) {
554          predict = (col == 0) ? ARGB_BLACK : current_row[col - 1];  // Left.
555        } else if (col == 0) {
556          predict = upper_row[col];  // Top.
557        } else {
558          predict = pred_func(current_row[col - 1], upper_row + col);
559        }
560        predict_diff = VP8LSubPixels(current_row[col], predict);
561        ++histo[0][predict_diff >> 24];
562        ++histo[1][((predict_diff >> 16) & 0xff)];
563        ++histo[2][((predict_diff >> 8) & 0xff)];
564        ++histo[3][(predict_diff & 0xff)];
565      }
566    }
567    cur_diff = PredictionCostSpatialHistogram(accumulated, histo);
568    if (cur_diff < best_diff) {
569      best_diff = cur_diff;
570      best_mode = mode;
571    }
572  }
573
574  return best_mode;
575}
576
577static void CopyTileWithPrediction(int width, int height,
578                                   int tile_x, int tile_y, int bits, int mode,
579                                   const uint32_t* const argb_scratch,
580                                   uint32_t* const argb) {
581  const int col_start = tile_x << bits;
582  const int row_start = tile_y << bits;
583  const int tile_size = 1 << bits;
584  const int ymax = (tile_size <= height - row_start) ?
585      tile_size : height - row_start;
586  const int xmax = (tile_size <= width - col_start) ?
587      tile_size : width - col_start;
588  const PredictorFunc pred_func = kPredictors[mode];
589  const uint32_t* current_row = argb_scratch;
590
591  int y;
592  for (y = 0; y < ymax; ++y) {
593    int x;
594    const int row = row_start + y;
595    const uint32_t* const upper_row = current_row;
596    current_row = upper_row + width;
597    for (x = 0; x < xmax; ++x) {
598      const int col = col_start + x;
599      const int pix = row * width + col;
600      uint32_t predict;
601      if (row == 0) {
602        predict = (col == 0) ? ARGB_BLACK : current_row[col - 1];  // Left.
603      } else if (col == 0) {
604        predict = upper_row[col];  // Top.
605      } else {
606        predict = pred_func(current_row[col - 1], upper_row + col);
607      }
608      argb[pix] = VP8LSubPixels(current_row[col], predict);
609    }
610  }
611}
612
613void VP8LResidualImage(int width, int height, int bits,
614                       uint32_t* const argb, uint32_t* const argb_scratch,
615                       uint32_t* const image) {
616  const int max_tile_size = 1 << bits;
617  const int tiles_per_row = VP8LSubSampleSize(width, bits);
618  const int tiles_per_col = VP8LSubSampleSize(height, bits);
619  uint32_t* const upper_row = argb_scratch;
620  uint32_t* const current_tile_rows = argb_scratch + width;
621  int tile_y;
622  int histo[4][256];
623  memset(histo, 0, sizeof(histo));
624  for (tile_y = 0; tile_y < tiles_per_col; ++tile_y) {
625    const int tile_y_offset = tile_y * max_tile_size;
626    const int this_tile_height =
627        (tile_y < tiles_per_col - 1) ? max_tile_size : height - tile_y_offset;
628    int tile_x;
629    if (tile_y > 0) {
630      memcpy(upper_row, current_tile_rows + (max_tile_size - 1) * width,
631             width * sizeof(*upper_row));
632    }
633    memcpy(current_tile_rows, &argb[tile_y_offset * width],
634           this_tile_height * width * sizeof(*current_tile_rows));
635    for (tile_x = 0; tile_x < tiles_per_row; ++tile_x) {
636      int pred;
637      int y;
638      const int tile_x_offset = tile_x * max_tile_size;
639      int all_x_max = tile_x_offset + max_tile_size;
640      if (all_x_max > width) {
641        all_x_max = width;
642      }
643      pred = GetBestPredictorForTile(width, height, tile_x, tile_y, bits, histo,
644                                     argb_scratch);
645      image[tile_y * tiles_per_row + tile_x] = 0xff000000u | (pred << 8);
646      CopyTileWithPrediction(width, height, tile_x, tile_y, bits, pred,
647                             argb_scratch, argb);
648      for (y = 0; y < max_tile_size; ++y) {
649        int ix;
650        int all_x;
651        int all_y = tile_y_offset + y;
652        if (all_y >= height) {
653          break;
654        }
655        ix = all_y * width + tile_x_offset;
656        for (all_x = tile_x_offset; all_x < all_x_max; ++all_x, ++ix) {
657          const uint32_t a = argb[ix];
658          ++histo[0][a >> 24];
659          ++histo[1][((a >> 16) & 0xff)];
660          ++histo[2][((a >> 8) & 0xff)];
661          ++histo[3][(a & 0xff)];
662        }
663      }
664    }
665  }
666}
667
668// Inverse prediction.
669static void PredictorInverseTransform(const VP8LTransform* const transform,
670                                      int y_start, int y_end, uint32_t* data) {
671  const int width = transform->xsize_;
672  if (y_start == 0) {  // First Row follows the L (mode=1) mode.
673    int x;
674    const uint32_t pred0 = Predictor0(data[-1], NULL);
675    AddPixelsEq(data, pred0);
676    for (x = 1; x < width; ++x) {
677      const uint32_t pred1 = Predictor1(data[x - 1], NULL);
678      AddPixelsEq(data + x, pred1);
679    }
680    data += width;
681    ++y_start;
682  }
683
684  {
685    int y = y_start;
686    const int mask = (1 << transform->bits_) - 1;
687    const int tiles_per_row = VP8LSubSampleSize(width, transform->bits_);
688    const uint32_t* pred_mode_base =
689        transform->data_ + (y >> transform->bits_) * tiles_per_row;
690
691    while (y < y_end) {
692      int x;
693      const uint32_t pred2 = Predictor2(data[-1], data - width);
694      const uint32_t* pred_mode_src = pred_mode_base;
695      PredictorFunc pred_func;
696
697      // First pixel follows the T (mode=2) mode.
698      AddPixelsEq(data, pred2);
699
700      // .. the rest:
701      pred_func = kPredictors[((*pred_mode_src++) >> 8) & 0xf];
702      for (x = 1; x < width; ++x) {
703        uint32_t pred;
704        if ((x & mask) == 0) {    // start of tile. Read predictor function.
705          pred_func = kPredictors[((*pred_mode_src++) >> 8) & 0xf];
706        }
707        pred = pred_func(data[x - 1], data + x - width);
708        AddPixelsEq(data + x, pred);
709      }
710      data += width;
711      ++y;
712      if ((y & mask) == 0) {   // Use the same mask, since tiles are squares.
713        pred_mode_base += tiles_per_row;
714      }
715    }
716  }
717}
718
719void VP8LSubtractGreenFromBlueAndRed(uint32_t* argb_data, int num_pixs) {
720  int i = 0;
721#if defined(WEBP_TARGET_HAS_SSE2)
722  const __m128i mask = _mm_set1_epi32(0x0000ff00);
723  for (; i + 4 < num_pixs; i += 4) {
724    const __m128i in = _mm_loadu_si128((__m128i*)&argb_data[i]);
725    const __m128i in_00g0 = _mm_and_si128(in, mask);     // 00g0|00g0|...
726    const __m128i in_0g00 = _mm_slli_epi32(in_00g0, 8);  // 0g00|0g00|...
727    const __m128i in_000g = _mm_srli_epi32(in_00g0, 8);  // 000g|000g|...
728    const __m128i in_0g0g = _mm_or_si128(in_0g00, in_000g);
729    const __m128i out = _mm_sub_epi8(in, in_0g0g);
730    _mm_storeu_si128((__m128i*)&argb_data[i], out);
731  }
732  // fallthrough and finish off with plain-C
733#endif
734  for (; i < num_pixs; ++i) {
735    const uint32_t argb = argb_data[i];
736    const uint32_t green = (argb >> 8) & 0xff;
737    const uint32_t new_r = (((argb >> 16) & 0xff) - green) & 0xff;
738    const uint32_t new_b = ((argb & 0xff) - green) & 0xff;
739    argb_data[i] = (argb & 0xff00ff00) | (new_r << 16) | new_b;
740  }
741}
742
743// Add green to blue and red channels (i.e. perform the inverse transform of
744// 'subtract green').
745static void AddGreenToBlueAndRed(const VP8LTransform* const transform,
746                                 int y_start, int y_end, uint32_t* data) {
747  const int width = transform->xsize_;
748  const uint32_t* const data_end = data + (y_end - y_start) * width;
749#if defined(WEBP_TARGET_HAS_SSE2)
750  const __m128i mask = _mm_set1_epi32(0x0000ff00);
751  for (; data + 4 < data_end; data += 4) {
752    const __m128i in = _mm_loadu_si128((__m128i*)data);
753    const __m128i in_00g0 = _mm_and_si128(in, mask);     // 00g0|00g0|...
754    const __m128i in_0g00 = _mm_slli_epi32(in_00g0, 8);  // 0g00|0g00|...
755    const __m128i in_000g = _mm_srli_epi32(in_00g0, 8);  // 000g|000g|...
756    const __m128i in_0g0g = _mm_or_si128(in_0g00, in_000g);
757    const __m128i out = _mm_add_epi8(in, in_0g0g);
758    _mm_storeu_si128((__m128i*)data, out);
759  }
760  // fallthrough and finish off with plain-C
761#endif
762  while (data < data_end) {
763    const uint32_t argb = *data;
764    const uint32_t green = ((argb >> 8) & 0xff);
765    uint32_t red_blue = (argb & 0x00ff00ffu);
766    red_blue += (green << 16) | green;
767    red_blue &= 0x00ff00ffu;
768    *data++ = (argb & 0xff00ff00u) | red_blue;
769  }
770}
771
772typedef struct {
773  // Note: the members are uint8_t, so that any negative values are
774  // automatically converted to "mod 256" values.
775  uint8_t green_to_red_;
776  uint8_t green_to_blue_;
777  uint8_t red_to_blue_;
778} Multipliers;
779
780static WEBP_INLINE void MultipliersClear(Multipliers* m) {
781  m->green_to_red_ = 0;
782  m->green_to_blue_ = 0;
783  m->red_to_blue_ = 0;
784}
785
786static WEBP_INLINE uint32_t ColorTransformDelta(int8_t color_pred,
787                                                int8_t color) {
788  return (uint32_t)((int)(color_pred) * color) >> 5;
789}
790
791static WEBP_INLINE void ColorCodeToMultipliers(uint32_t color_code,
792                                               Multipliers* const m) {
793  m->green_to_red_  = (color_code >>  0) & 0xff;
794  m->green_to_blue_ = (color_code >>  8) & 0xff;
795  m->red_to_blue_   = (color_code >> 16) & 0xff;
796}
797
798static WEBP_INLINE uint32_t MultipliersToColorCode(Multipliers* const m) {
799  return 0xff000000u |
800         ((uint32_t)(m->red_to_blue_) << 16) |
801         ((uint32_t)(m->green_to_blue_) << 8) |
802         m->green_to_red_;
803}
804
805static WEBP_INLINE uint32_t TransformColor(const Multipliers* const m,
806                                           uint32_t argb, int inverse) {
807  const uint32_t green = argb >> 8;
808  const uint32_t red = argb >> 16;
809  uint32_t new_red = red;
810  uint32_t new_blue = argb;
811
812  if (inverse) {
813    new_red += ColorTransformDelta(m->green_to_red_, green);
814    new_red &= 0xff;
815    new_blue += ColorTransformDelta(m->green_to_blue_, green);
816    new_blue += ColorTransformDelta(m->red_to_blue_, new_red);
817    new_blue &= 0xff;
818  } else {
819    new_red -= ColorTransformDelta(m->green_to_red_, green);
820    new_red &= 0xff;
821    new_blue -= ColorTransformDelta(m->green_to_blue_, green);
822    new_blue -= ColorTransformDelta(m->red_to_blue_, red);
823    new_blue &= 0xff;
824  }
825  return (argb & 0xff00ff00u) | (new_red << 16) | (new_blue);
826}
827
828static WEBP_INLINE uint8_t TransformColorRed(uint8_t green_to_red,
829                                             uint32_t argb) {
830  const uint32_t green = argb >> 8;
831  uint32_t new_red = argb >> 16;
832  new_red -= ColorTransformDelta(green_to_red, green);
833  return (new_red & 0xff);
834}
835
836static WEBP_INLINE uint8_t TransformColorBlue(uint8_t green_to_blue,
837                                              uint8_t red_to_blue,
838                                              uint32_t argb) {
839  const uint32_t green = argb >> 8;
840  const uint32_t red = argb >> 16;
841  uint8_t new_blue = argb;
842  new_blue -= ColorTransformDelta(green_to_blue, green);
843  new_blue -= ColorTransformDelta(red_to_blue, red);
844  return (new_blue & 0xff);
845}
846
847static WEBP_INLINE int SkipRepeatedPixels(const uint32_t* const argb,
848                                          int ix, int xsize) {
849  const uint32_t v = argb[ix];
850  if (ix >= xsize + 3) {
851    if (v == argb[ix - xsize] &&
852        argb[ix - 1] == argb[ix - xsize - 1] &&
853        argb[ix - 2] == argb[ix - xsize - 2] &&
854        argb[ix - 3] == argb[ix - xsize - 3]) {
855      return 1;
856    }
857    return v == argb[ix - 3] && v == argb[ix - 2] && v == argb[ix - 1];
858  } else if (ix >= 3) {
859    return v == argb[ix - 3] && v == argb[ix - 2] && v == argb[ix - 1];
860  }
861  return 0;
862}
863
864static float PredictionCostCrossColor(const int accumulated[256],
865                                      const int counts[256]) {
866  // Favor low entropy, locally and globally.
867  // Favor small absolute values for PredictionCostSpatial
868  static const double kExpValue = 2.4;
869  return CombinedShannonEntropy(counts, accumulated, 256) +
870         PredictionCostSpatial(counts, 3, kExpValue);
871}
872
873static Multipliers GetBestColorTransformForTile(
874    int tile_x, int tile_y, int bits,
875    Multipliers prevX,
876    Multipliers prevY,
877    int step, int xsize, int ysize,
878    int* accumulated_red_histo,
879    int* accumulated_blue_histo,
880    const uint32_t* const argb) {
881  float best_diff = MAX_DIFF_COST;
882  float cur_diff;
883  const int halfstep = step / 2;
884  const int max_tile_size = 1 << bits;
885  const int tile_y_offset = tile_y * max_tile_size;
886  const int tile_x_offset = tile_x * max_tile_size;
887  int green_to_red;
888  int green_to_blue;
889  int red_to_blue;
890  int all_x_max = tile_x_offset + max_tile_size;
891  int all_y_max = tile_y_offset + max_tile_size;
892  Multipliers best_tx;
893  MultipliersClear(&best_tx);
894  if (all_x_max > xsize) {
895    all_x_max = xsize;
896  }
897  if (all_y_max > ysize) {
898    all_y_max = ysize;
899  }
900
901  for (green_to_red = -64; green_to_red <= 64; green_to_red += halfstep) {
902    int histo[256] = { 0 };
903    int all_y;
904
905    for (all_y = tile_y_offset; all_y < all_y_max; ++all_y) {
906      int ix = all_y * xsize + tile_x_offset;
907      int all_x;
908      for (all_x = tile_x_offset; all_x < all_x_max; ++all_x, ++ix) {
909        if (SkipRepeatedPixels(argb, ix, xsize)) {
910          continue;
911        }
912        ++histo[TransformColorRed(green_to_red, argb[ix])];  // red.
913      }
914    }
915    cur_diff = PredictionCostCrossColor(&accumulated_red_histo[0], &histo[0]);
916    if ((uint8_t)green_to_red == prevX.green_to_red_) {
917      cur_diff -= 3;  // favor keeping the areas locally similar
918    }
919    if ((uint8_t)green_to_red == prevY.green_to_red_) {
920      cur_diff -= 3;  // favor keeping the areas locally similar
921    }
922    if (green_to_red == 0) {
923      cur_diff -= 3;
924    }
925    if (cur_diff < best_diff) {
926      best_diff = cur_diff;
927      best_tx.green_to_red_ = green_to_red;
928    }
929  }
930  best_diff = MAX_DIFF_COST;
931  for (green_to_blue = -32; green_to_blue <= 32; green_to_blue += step) {
932    for (red_to_blue = -32; red_to_blue <= 32; red_to_blue += step) {
933      int all_y;
934      int histo[256] = { 0 };
935      for (all_y = tile_y_offset; all_y < all_y_max; ++all_y) {
936        int all_x;
937        int ix = all_y * xsize + tile_x_offset;
938        for (all_x = tile_x_offset; all_x < all_x_max; ++all_x, ++ix) {
939          if (SkipRepeatedPixels(argb, ix, xsize)) {
940            continue;
941          }
942          ++histo[TransformColorBlue(green_to_blue, red_to_blue, argb[ix])];
943        }
944      }
945      cur_diff =
946          PredictionCostCrossColor(&accumulated_blue_histo[0], &histo[0]);
947      if ((uint8_t)green_to_blue == prevX.green_to_blue_) {
948        cur_diff -= 3;  // favor keeping the areas locally similar
949      }
950      if ((uint8_t)green_to_blue == prevY.green_to_blue_) {
951        cur_diff -= 3;  // favor keeping the areas locally similar
952      }
953      if ((uint8_t)red_to_blue == prevX.red_to_blue_) {
954        cur_diff -= 3;  // favor keeping the areas locally similar
955      }
956      if ((uint8_t)red_to_blue == prevY.red_to_blue_) {
957        cur_diff -= 3;  // favor keeping the areas locally similar
958      }
959      if (green_to_blue == 0) {
960        cur_diff -= 3;
961      }
962      if (red_to_blue == 0) {
963        cur_diff -= 3;
964      }
965      if (cur_diff < best_diff) {
966        best_diff = cur_diff;
967        best_tx.green_to_blue_ = green_to_blue;
968        best_tx.red_to_blue_ = red_to_blue;
969      }
970    }
971  }
972  return best_tx;
973}
974
975static void CopyTileWithColorTransform(int xsize, int ysize,
976                                       int tile_x, int tile_y, int bits,
977                                       Multipliers color_transform,
978                                       uint32_t* const argb) {
979  int y;
980  int xscan = 1 << bits;
981  int yscan = 1 << bits;
982  tile_x <<= bits;
983  tile_y <<= bits;
984  if (xscan > xsize - tile_x) {
985    xscan = xsize - tile_x;
986  }
987  if (yscan > ysize - tile_y) {
988    yscan = ysize - tile_y;
989  }
990  yscan += tile_y;
991  for (y = tile_y; y < yscan; ++y) {
992    int ix = y * xsize + tile_x;
993    const int end_ix = ix + xscan;
994    for (; ix < end_ix; ++ix) {
995      argb[ix] = TransformColor(&color_transform, argb[ix], 0);
996    }
997  }
998}
999
1000void VP8LColorSpaceTransform(int width, int height, int bits, int step,
1001                             uint32_t* const argb, uint32_t* image) {
1002  const int max_tile_size = 1 << bits;
1003  int tile_xsize = VP8LSubSampleSize(width, bits);
1004  int tile_ysize = VP8LSubSampleSize(height, bits);
1005  int accumulated_red_histo[256] = { 0 };
1006  int accumulated_blue_histo[256] = { 0 };
1007  int tile_y;
1008  int tile_x;
1009  Multipliers prevX;
1010  Multipliers prevY;
1011  MultipliersClear(&prevY);
1012  MultipliersClear(&prevX);
1013  for (tile_y = 0; tile_y < tile_ysize; ++tile_y) {
1014    for (tile_x = 0; tile_x < tile_xsize; ++tile_x) {
1015      Multipliers color_transform;
1016      int all_x_max;
1017      int y;
1018      const int tile_y_offset = tile_y * max_tile_size;
1019      const int tile_x_offset = tile_x * max_tile_size;
1020      if (tile_y != 0) {
1021        ColorCodeToMultipliers(image[tile_y * tile_xsize + tile_x - 1], &prevX);
1022        ColorCodeToMultipliers(image[(tile_y - 1) * tile_xsize + tile_x],
1023                               &prevY);
1024      } else if (tile_x != 0) {
1025        ColorCodeToMultipliers(image[tile_y * tile_xsize + tile_x - 1], &prevX);
1026      }
1027      color_transform =
1028          GetBestColorTransformForTile(tile_x, tile_y, bits,
1029                                       prevX, prevY,
1030                                       step, width, height,
1031                                       &accumulated_red_histo[0],
1032                                       &accumulated_blue_histo[0],
1033                                       argb);
1034      image[tile_y * tile_xsize + tile_x] =
1035          MultipliersToColorCode(&color_transform);
1036      CopyTileWithColorTransform(width, height, tile_x, tile_y, bits,
1037                                 color_transform, argb);
1038
1039      // Gather accumulated histogram data.
1040      all_x_max = tile_x_offset + max_tile_size;
1041      if (all_x_max > width) {
1042        all_x_max = width;
1043      }
1044      for (y = 0; y < max_tile_size; ++y) {
1045        int ix;
1046        int all_x;
1047        int all_y = tile_y_offset + y;
1048        if (all_y >= height) {
1049          break;
1050        }
1051        ix = all_y * width + tile_x_offset;
1052        for (all_x = tile_x_offset; all_x < all_x_max; ++all_x, ++ix) {
1053          if (ix >= 2 &&
1054              argb[ix] == argb[ix - 2] &&
1055              argb[ix] == argb[ix - 1]) {
1056            continue;  // repeated pixels are handled by backward references
1057          }
1058          if (ix >= width + 2 &&
1059              argb[ix - 2] == argb[ix - width - 2] &&
1060              argb[ix - 1] == argb[ix - width - 1] &&
1061              argb[ix] == argb[ix - width]) {
1062            continue;  // repeated pixels are handled by backward references
1063          }
1064          ++accumulated_red_histo[(argb[ix] >> 16) & 0xff];
1065          ++accumulated_blue_histo[argb[ix] & 0xff];
1066        }
1067      }
1068    }
1069  }
1070}
1071
1072// Color space inverse transform.
1073static void ColorSpaceInverseTransform(const VP8LTransform* const transform,
1074                                       int y_start, int y_end, uint32_t* data) {
1075  const int width = transform->xsize_;
1076  const int mask = (1 << transform->bits_) - 1;
1077  const int tiles_per_row = VP8LSubSampleSize(width, transform->bits_);
1078  int y = y_start;
1079  const uint32_t* pred_row =
1080      transform->data_ + (y >> transform->bits_) * tiles_per_row;
1081
1082  while (y < y_end) {
1083    const uint32_t* pred = pred_row;
1084    Multipliers m = { 0, 0, 0 };
1085    int x;
1086
1087    for (x = 0; x < width; ++x) {
1088      if ((x & mask) == 0) ColorCodeToMultipliers(*pred++, &m);
1089      data[x] = TransformColor(&m, data[x], 1);
1090    }
1091    data += width;
1092    ++y;
1093    if ((y & mask) == 0) pred_row += tiles_per_row;;
1094  }
1095}
1096
1097// Separate out pixels packed together using pixel-bundling.
1098// We define two methods for ARGB data (uint32_t) and alpha-only data (uint8_t).
1099#define COLOR_INDEX_INVERSE(FUNC_NAME, TYPE, GET_INDEX, GET_VALUE)             \
1100void FUNC_NAME(const VP8LTransform* const transform,                           \
1101               int y_start, int y_end, const TYPE* src, TYPE* dst) {           \
1102  int y;                                                                       \
1103  const int bits_per_pixel = 8 >> transform->bits_;                            \
1104  const int width = transform->xsize_;                                         \
1105  const uint32_t* const color_map = transform->data_;                          \
1106  if (bits_per_pixel < 8) {                                                    \
1107    const int pixels_per_byte = 1 << transform->bits_;                         \
1108    const int count_mask = pixels_per_byte - 1;                                \
1109    const uint32_t bit_mask = (1 << bits_per_pixel) - 1;                       \
1110    for (y = y_start; y < y_end; ++y) {                                        \
1111      uint32_t packed_pixels = 0;                                              \
1112      int x;                                                                   \
1113      for (x = 0; x < width; ++x) {                                            \
1114        /* We need to load fresh 'packed_pixels' once every                */  \
1115        /* 'pixels_per_byte' increments of x. Fortunately, pixels_per_byte */  \
1116        /* is a power of 2, so can just use a mask for that, instead of    */  \
1117        /* decrementing a counter.                                         */  \
1118        if ((x & count_mask) == 0) packed_pixels = GET_INDEX(*src++);          \
1119        *dst++ = GET_VALUE(color_map[packed_pixels & bit_mask]);               \
1120        packed_pixels >>= bits_per_pixel;                                      \
1121      }                                                                        \
1122    }                                                                          \
1123  } else {                                                                     \
1124    for (y = y_start; y < y_end; ++y) {                                        \
1125      int x;                                                                   \
1126      for (x = 0; x < width; ++x) {                                            \
1127        *dst++ = GET_VALUE(color_map[GET_INDEX(*src++)]);                      \
1128      }                                                                        \
1129    }                                                                          \
1130  }                                                                            \
1131}
1132
1133static WEBP_INLINE uint32_t GetARGBIndex(uint32_t idx) {
1134  return (idx >> 8) & 0xff;
1135}
1136
1137static WEBP_INLINE uint8_t GetAlphaIndex(uint8_t idx) {
1138  return idx;
1139}
1140
1141static WEBP_INLINE uint32_t GetARGBValue(uint32_t val) {
1142  return val;
1143}
1144
1145static WEBP_INLINE uint8_t GetAlphaValue(uint32_t val) {
1146  return (val >> 8) & 0xff;
1147}
1148
1149static COLOR_INDEX_INVERSE(ColorIndexInverseTransform, uint32_t, GetARGBIndex,
1150                           GetARGBValue)
1151COLOR_INDEX_INVERSE(VP8LColorIndexInverseTransformAlpha, uint8_t, GetAlphaIndex,
1152                    GetAlphaValue)
1153
1154#undef COLOR_INDEX_INVERSE
1155
1156void VP8LInverseTransform(const VP8LTransform* const transform,
1157                          int row_start, int row_end,
1158                          const uint32_t* const in, uint32_t* const out) {
1159  assert(row_start < row_end);
1160  assert(row_end <= transform->ysize_);
1161  switch (transform->type_) {
1162    case SUBTRACT_GREEN:
1163      AddGreenToBlueAndRed(transform, row_start, row_end, out);
1164      break;
1165    case PREDICTOR_TRANSFORM:
1166      PredictorInverseTransform(transform, row_start, row_end, out);
1167      if (row_end != transform->ysize_) {
1168        // The last predicted row in this iteration will be the top-pred row
1169        // for the first row in next iteration.
1170        const int width = transform->xsize_;
1171        memcpy(out - width, out + (row_end - row_start - 1) * width,
1172               width * sizeof(*out));
1173      }
1174      break;
1175    case CROSS_COLOR_TRANSFORM:
1176      ColorSpaceInverseTransform(transform, row_start, row_end, out);
1177      break;
1178    case COLOR_INDEXING_TRANSFORM:
1179      if (in == out && transform->bits_ > 0) {
1180        // Move packed pixels to the end of unpacked region, so that unpacking
1181        // can occur seamlessly.
1182        // Also, note that this is the only transform that applies on
1183        // the effective width of VP8LSubSampleSize(xsize_, bits_). All other
1184        // transforms work on effective width of xsize_.
1185        const int out_stride = (row_end - row_start) * transform->xsize_;
1186        const int in_stride = (row_end - row_start) *
1187            VP8LSubSampleSize(transform->xsize_, transform->bits_);
1188        uint32_t* const src = out + out_stride - in_stride;
1189        memmove(src, out, in_stride * sizeof(*src));
1190        ColorIndexInverseTransform(transform, row_start, row_end, src, out);
1191      } else {
1192        ColorIndexInverseTransform(transform, row_start, row_end, in, out);
1193      }
1194      break;
1195  }
1196}
1197
1198//------------------------------------------------------------------------------
1199// Color space conversion.
1200
1201static int is_big_endian(void) {
1202  static const union {
1203    uint16_t w;
1204    uint8_t b[2];
1205  } tmp = { 1 };
1206  return (tmp.b[0] != 1);
1207}
1208
1209static void ConvertBGRAToRGB(const uint32_t* src,
1210                             int num_pixels, uint8_t* dst) {
1211  const uint32_t* const src_end = src + num_pixels;
1212  while (src < src_end) {
1213    const uint32_t argb = *src++;
1214    *dst++ = (argb >> 16) & 0xff;
1215    *dst++ = (argb >>  8) & 0xff;
1216    *dst++ = (argb >>  0) & 0xff;
1217  }
1218}
1219
1220static void ConvertBGRAToRGBA(const uint32_t* src,
1221                              int num_pixels, uint8_t* dst) {
1222  const uint32_t* const src_end = src + num_pixels;
1223  while (src < src_end) {
1224    const uint32_t argb = *src++;
1225    *dst++ = (argb >> 16) & 0xff;
1226    *dst++ = (argb >>  8) & 0xff;
1227    *dst++ = (argb >>  0) & 0xff;
1228    *dst++ = (argb >> 24) & 0xff;
1229  }
1230}
1231
1232static void ConvertBGRAToRGBA4444(const uint32_t* src,
1233                                  int num_pixels, uint8_t* dst) {
1234  const uint32_t* const src_end = src + num_pixels;
1235  while (src < src_end) {
1236    const uint32_t argb = *src++;
1237    const uint8_t rg = ((argb >> 16) & 0xf0) | ((argb >> 12) & 0xf);
1238    const uint8_t ba = ((argb >>  0) & 0xf0) | ((argb >> 28) & 0xf);
1239#ifdef WEBP_SWAP_16BIT_CSP
1240    *dst++ = ba;
1241    *dst++ = rg;
1242#else
1243    *dst++ = rg;
1244    *dst++ = ba;
1245#endif
1246  }
1247}
1248
1249static void ConvertBGRAToRGB565(const uint32_t* src,
1250                                int num_pixels, uint8_t* dst) {
1251  const uint32_t* const src_end = src + num_pixels;
1252  while (src < src_end) {
1253    const uint32_t argb = *src++;
1254    const uint8_t rg = ((argb >> 16) & 0xf8) | ((argb >> 13) & 0x7);
1255    const uint8_t gb = ((argb >>  5) & 0xe0) | ((argb >>  3) & 0x1f);
1256#ifdef WEBP_SWAP_16BIT_CSP
1257    *dst++ = gb;
1258    *dst++ = rg;
1259#else
1260    *dst++ = rg;
1261    *dst++ = gb;
1262#endif
1263  }
1264}
1265
1266static void ConvertBGRAToBGR(const uint32_t* src,
1267                             int num_pixels, uint8_t* dst) {
1268  const uint32_t* const src_end = src + num_pixels;
1269  while (src < src_end) {
1270    const uint32_t argb = *src++;
1271    *dst++ = (argb >>  0) & 0xff;
1272    *dst++ = (argb >>  8) & 0xff;
1273    *dst++ = (argb >> 16) & 0xff;
1274  }
1275}
1276
1277static void CopyOrSwap(const uint32_t* src, int num_pixels, uint8_t* dst,
1278                       int swap_on_big_endian) {
1279  if (is_big_endian() == swap_on_big_endian) {
1280    const uint32_t* const src_end = src + num_pixels;
1281    while (src < src_end) {
1282      uint32_t argb = *src++;
1283
1284#if !defined(__BIG_ENDIAN__)
1285#if !defined(WEBP_REFERENCE_IMPLEMENTATION)
1286#if defined(__i386__) || defined(__x86_64__)
1287      __asm__ volatile("bswap %0" : "=r"(argb) : "0"(argb));
1288      *(uint32_t*)dst = argb;
1289#elif defined(_MSC_VER)
1290      argb = _byteswap_ulong(argb);
1291      *(uint32_t*)dst = argb;
1292#else
1293      dst[0] = (argb >> 24) & 0xff;
1294      dst[1] = (argb >> 16) & 0xff;
1295      dst[2] = (argb >>  8) & 0xff;
1296      dst[3] = (argb >>  0) & 0xff;
1297#endif
1298#else  // WEBP_REFERENCE_IMPLEMENTATION
1299      dst[0] = (argb >> 24) & 0xff;
1300      dst[1] = (argb >> 16) & 0xff;
1301      dst[2] = (argb >>  8) & 0xff;
1302      dst[3] = (argb >>  0) & 0xff;
1303#endif
1304#else  // __BIG_ENDIAN__
1305      dst[0] = (argb >>  0) & 0xff;
1306      dst[1] = (argb >>  8) & 0xff;
1307      dst[2] = (argb >> 16) & 0xff;
1308      dst[3] = (argb >> 24) & 0xff;
1309#endif
1310      dst += sizeof(argb);
1311    }
1312  } else {
1313    memcpy(dst, src, num_pixels * sizeof(*src));
1314  }
1315}
1316
1317void VP8LConvertFromBGRA(const uint32_t* const in_data, int num_pixels,
1318                         WEBP_CSP_MODE out_colorspace, uint8_t* const rgba) {
1319  switch (out_colorspace) {
1320    case MODE_RGB:
1321      ConvertBGRAToRGB(in_data, num_pixels, rgba);
1322      break;
1323    case MODE_RGBA:
1324      ConvertBGRAToRGBA(in_data, num_pixels, rgba);
1325      break;
1326    case MODE_rgbA:
1327      ConvertBGRAToRGBA(in_data, num_pixels, rgba);
1328      WebPApplyAlphaMultiply(rgba, 0, num_pixels, 1, 0);
1329      break;
1330    case MODE_BGR:
1331      ConvertBGRAToBGR(in_data, num_pixels, rgba);
1332      break;
1333    case MODE_BGRA:
1334      CopyOrSwap(in_data, num_pixels, rgba, 1);
1335      break;
1336    case MODE_bgrA:
1337      CopyOrSwap(in_data, num_pixels, rgba, 1);
1338      WebPApplyAlphaMultiply(rgba, 0, num_pixels, 1, 0);
1339      break;
1340    case MODE_ARGB:
1341      CopyOrSwap(in_data, num_pixels, rgba, 0);
1342      break;
1343    case MODE_Argb:
1344      CopyOrSwap(in_data, num_pixels, rgba, 0);
1345      WebPApplyAlphaMultiply(rgba, 1, num_pixels, 1, 0);
1346      break;
1347    case MODE_RGBA_4444:
1348      ConvertBGRAToRGBA4444(in_data, num_pixels, rgba);
1349      break;
1350    case MODE_rgbA_4444:
1351      ConvertBGRAToRGBA4444(in_data, num_pixels, rgba);
1352      WebPApplyAlphaMultiply4444(rgba, num_pixels, 1, 0);
1353      break;
1354    case MODE_RGB_565:
1355      ConvertBGRAToRGB565(in_data, num_pixels, rgba);
1356      break;
1357    default:
1358      assert(0);          // Code flow should not reach here.
1359  }
1360}
1361
1362// Bundles multiple (1, 2, 4 or 8) pixels into a single pixel.
1363void VP8LBundleColorMap(const uint8_t* const row, int width,
1364                        int xbits, uint32_t* const dst) {
1365  int x;
1366  if (xbits > 0) {
1367    const int bit_depth = 1 << (3 - xbits);
1368    const int mask = (1 << xbits) - 1;
1369    uint32_t code = 0xff000000;
1370    for (x = 0; x < width; ++x) {
1371      const int xsub = x & mask;
1372      if (xsub == 0) {
1373        code = 0xff000000;
1374      }
1375      code |= row[x] << (8 + bit_depth * xsub);
1376      dst[x >> xbits] = code;
1377    }
1378  } else {
1379    for (x = 0; x < width; ++x) dst[x] = 0xff000000 | (row[x] << 8);
1380  }
1381}
1382
1383//------------------------------------------------------------------------------
1384
1385#if defined(__cplusplus) || defined(c_plusplus)
1386}    // extern "C"
1387#endif
1388