1 // Copyright 2015 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 // MIPS version of lossless functions
11 //
12 // Author(s): Djordje Pesut (djordje.pesut@imgtec.com)
13 // Jovan Zelincevic (jovan.zelincevic@imgtec.com)
14
15 #include "./dsp.h"
16 #include "./lossless.h"
17
18 #if defined(WEBP_USE_MIPS32)
19
20 #include <assert.h>
21 #include <math.h>
22 #include <stdlib.h>
23 #include <string.h>
24
FastSLog2Slow(uint32_t v)25 static float FastSLog2Slow(uint32_t v) {
26 assert(v >= LOG_LOOKUP_IDX_MAX);
27 if (v < APPROX_LOG_WITH_CORRECTION_MAX) {
28 uint32_t log_cnt, y, correction;
29 const int c24 = 24;
30 const float v_f = (float)v;
31 uint32_t temp;
32
33 // Xf = 256 = 2^8
34 // log_cnt is index of leading one in upper 24 bits
35 __asm__ volatile(
36 "clz %[log_cnt], %[v] \n\t"
37 "addiu %[y], $zero, 1 \n\t"
38 "subu %[log_cnt], %[c24], %[log_cnt] \n\t"
39 "sllv %[y], %[y], %[log_cnt] \n\t"
40 "srlv %[temp], %[v], %[log_cnt] \n\t"
41 : [log_cnt]"=&r"(log_cnt), [y]"=&r"(y),
42 [temp]"=r"(temp)
43 : [c24]"r"(c24), [v]"r"(v)
44 );
45
46 // vf = (2^log_cnt) * Xf; where y = 2^log_cnt and Xf < 256
47 // Xf = floor(Xf) * (1 + (v % y) / v)
48 // log2(Xf) = log2(floor(Xf)) + log2(1 + (v % y) / v)
49 // The correction factor: log(1 + d) ~ d; for very small d values, so
50 // log2(1 + (v % y) / v) ~ LOG_2_RECIPROCAL * (v % y)/v
51 // LOG_2_RECIPROCAL ~ 23/16
52
53 // (v % y) = (v % 2^log_cnt) = v & (2^log_cnt - 1)
54 correction = (23 * (v & (y - 1))) >> 4;
55 return v_f * (kLog2Table[temp] + log_cnt) + correction;
56 } else {
57 return (float)(LOG_2_RECIPROCAL * v * log((double)v));
58 }
59 }
60
FastLog2Slow(uint32_t v)61 static float FastLog2Slow(uint32_t v) {
62 assert(v >= LOG_LOOKUP_IDX_MAX);
63 if (v < APPROX_LOG_WITH_CORRECTION_MAX) {
64 uint32_t log_cnt, y;
65 const int c24 = 24;
66 double log_2;
67 uint32_t temp;
68
69 __asm__ volatile(
70 "clz %[log_cnt], %[v] \n\t"
71 "addiu %[y], $zero, 1 \n\t"
72 "subu %[log_cnt], %[c24], %[log_cnt] \n\t"
73 "sllv %[y], %[y], %[log_cnt] \n\t"
74 "srlv %[temp], %[v], %[log_cnt] \n\t"
75 : [log_cnt]"=&r"(log_cnt), [y]"=&r"(y),
76 [temp]"=r"(temp)
77 : [c24]"r"(c24), [v]"r"(v)
78 );
79
80 log_2 = kLog2Table[temp] + log_cnt;
81 if (v >= APPROX_LOG_MAX) {
82 // Since the division is still expensive, add this correction factor only
83 // for large values of 'v'.
84
85 const uint32_t correction = (23 * (v & (y - 1))) >> 4;
86 log_2 += (double)correction / v;
87 }
88 return (float)log_2;
89 } else {
90 return (float)(LOG_2_RECIPROCAL * log((double)v));
91 }
92 }
93
94 // C version of this function:
95 // int i = 0;
96 // int64_t cost = 0;
97 // const uint32_t* pop = &population[4];
98 // const uint32_t* LoopEnd = &population[length];
99 // while (pop != LoopEnd) {
100 // ++i;
101 // cost += i * *pop;
102 // cost += i * *(pop + 1);
103 // pop += 2;
104 // }
105 // return (double)cost;
ExtraCost(const uint32_t * const population,int length)106 static double ExtraCost(const uint32_t* const population, int length) {
107 int i, temp0, temp1;
108 const uint32_t* pop = &population[4];
109 const uint32_t* const LoopEnd = &population[length];
110
111 __asm__ volatile(
112 "mult $zero, $zero \n\t"
113 "xor %[i], %[i], %[i] \n\t"
114 "beq %[pop], %[LoopEnd], 2f \n\t"
115 "1: \n\t"
116 "lw %[temp0], 0(%[pop]) \n\t"
117 "lw %[temp1], 4(%[pop]) \n\t"
118 "addiu %[i], %[i], 1 \n\t"
119 "addiu %[pop], %[pop], 8 \n\t"
120 "madd %[i], %[temp0] \n\t"
121 "madd %[i], %[temp1] \n\t"
122 "bne %[pop], %[LoopEnd], 1b \n\t"
123 "2: \n\t"
124 "mfhi %[temp0] \n\t"
125 "mflo %[temp1] \n\t"
126 : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1),
127 [i]"=&r"(i), [pop]"+r"(pop)
128 : [LoopEnd]"r"(LoopEnd)
129 : "memory", "hi", "lo"
130 );
131
132 return (double)((int64_t)temp0 << 32 | temp1);
133 }
134
135 // C version of this function:
136 // int i = 0;
137 // int64_t cost = 0;
138 // const uint32_t* pX = &X[4];
139 // const uint32_t* pY = &Y[4];
140 // const uint32_t* LoopEnd = &X[length];
141 // while (pX != LoopEnd) {
142 // const uint32_t xy0 = *pX + *pY;
143 // const uint32_t xy1 = *(pX + 1) + *(pY + 1);
144 // ++i;
145 // cost += i * xy0;
146 // cost += i * xy1;
147 // pX += 2;
148 // pY += 2;
149 // }
150 // return (double)cost;
ExtraCostCombined(const uint32_t * const X,const uint32_t * const Y,int length)151 static double ExtraCostCombined(const uint32_t* const X,
152 const uint32_t* const Y, int length) {
153 int i, temp0, temp1, temp2, temp3;
154 const uint32_t* pX = &X[4];
155 const uint32_t* pY = &Y[4];
156 const uint32_t* const LoopEnd = &X[length];
157
158 __asm__ volatile(
159 "mult $zero, $zero \n\t"
160 "xor %[i], %[i], %[i] \n\t"
161 "beq %[pX], %[LoopEnd], 2f \n\t"
162 "1: \n\t"
163 "lw %[temp0], 0(%[pX]) \n\t"
164 "lw %[temp1], 0(%[pY]) \n\t"
165 "lw %[temp2], 4(%[pX]) \n\t"
166 "lw %[temp3], 4(%[pY]) \n\t"
167 "addiu %[i], %[i], 1 \n\t"
168 "addu %[temp0], %[temp0], %[temp1] \n\t"
169 "addu %[temp2], %[temp2], %[temp3] \n\t"
170 "addiu %[pX], %[pX], 8 \n\t"
171 "addiu %[pY], %[pY], 8 \n\t"
172 "madd %[i], %[temp0] \n\t"
173 "madd %[i], %[temp2] \n\t"
174 "bne %[pX], %[LoopEnd], 1b \n\t"
175 "2: \n\t"
176 "mfhi %[temp0] \n\t"
177 "mflo %[temp1] \n\t"
178 : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1),
179 [temp2]"=&r"(temp2), [temp3]"=&r"(temp3),
180 [i]"=&r"(i), [pX]"+r"(pX), [pY]"+r"(pY)
181 : [LoopEnd]"r"(LoopEnd)
182 : "memory", "hi", "lo"
183 );
184
185 return (double)((int64_t)temp0 << 32 | temp1);
186 }
187
188 #define HUFFMAN_COST_PASS \
189 __asm__ volatile( \
190 "sll %[temp1], %[temp0], 3 \n\t" \
191 "addiu %[temp3], %[streak], -3 \n\t" \
192 "addu %[temp2], %[pstreaks], %[temp1] \n\t" \
193 "blez %[temp3], 1f \n\t" \
194 "srl %[temp1], %[temp1], 1 \n\t" \
195 "addu %[temp3], %[pcnts], %[temp1] \n\t" \
196 "lw %[temp0], 4(%[temp2]) \n\t" \
197 "lw %[temp1], 0(%[temp3]) \n\t" \
198 "addu %[temp0], %[temp0], %[streak] \n\t" \
199 "addiu %[temp1], %[temp1], 1 \n\t" \
200 "sw %[temp0], 4(%[temp2]) \n\t" \
201 "sw %[temp1], 0(%[temp3]) \n\t" \
202 "b 2f \n\t" \
203 "1: \n\t" \
204 "lw %[temp0], 0(%[temp2]) \n\t" \
205 "addu %[temp0], %[temp0], %[streak] \n\t" \
206 "sw %[temp0], 0(%[temp2]) \n\t" \
207 "2: \n\t" \
208 : [temp1]"=&r"(temp1), [temp2]"=&r"(temp2), \
209 [temp3]"=&r"(temp3), [temp0]"+r"(temp0) \
210 : [pstreaks]"r"(pstreaks), [pcnts]"r"(pcnts), \
211 [streak]"r"(streak) \
212 : "memory" \
213 );
214
215 // Returns the various RLE counts
GetEntropyUnrefinedHelper(uint32_t val,int i,uint32_t * const val_prev,int * const i_prev,VP8LBitEntropy * const bit_entropy,VP8LStreaks * const stats)216 static WEBP_INLINE void GetEntropyUnrefinedHelper(
217 uint32_t val, int i, uint32_t* const val_prev, int* const i_prev,
218 VP8LBitEntropy* const bit_entropy, VP8LStreaks* const stats) {
219 int* const pstreaks = &stats->streaks[0][0];
220 int* const pcnts = &stats->counts[0];
221 int temp0, temp1, temp2, temp3;
222 const int streak = i - *i_prev;
223
224 // Gather info for the bit entropy.
225 if (*val_prev != 0) {
226 bit_entropy->sum += (*val_prev) * streak;
227 bit_entropy->nonzeros += streak;
228 bit_entropy->nonzero_code = *i_prev;
229 bit_entropy->entropy -= VP8LFastSLog2(*val_prev) * streak;
230 if (bit_entropy->max_val < *val_prev) {
231 bit_entropy->max_val = *val_prev;
232 }
233 }
234
235 // Gather info for the Huffman cost.
236 temp0 = (*val_prev != 0);
237 HUFFMAN_COST_PASS
238
239 *val_prev = val;
240 *i_prev = i;
241 }
242
243 #define ASM_START \
244 __asm__ volatile( \
245 ".set push \n\t" \
246 ".set at \n\t" \
247 ".set macro \n\t" \
248 "1: \n\t"
249
250 // P2 = P0 + P1
251 // A..D - offsets
252 // E - temp variable to tell macro
253 // if pointer should be incremented
254 // literal_ and successive histograms could be unaligned
255 // so we must use ulw and usw
256 #define ADD_TO_OUT(A, B, C, D, E, P0, P1, P2) \
257 "ulw %[temp0], " #A "(%[" #P0 "]) \n\t" \
258 "ulw %[temp1], " #B "(%[" #P0 "]) \n\t" \
259 "ulw %[temp2], " #C "(%[" #P0 "]) \n\t" \
260 "ulw %[temp3], " #D "(%[" #P0 "]) \n\t" \
261 "ulw %[temp4], " #A "(%[" #P1 "]) \n\t" \
262 "ulw %[temp5], " #B "(%[" #P1 "]) \n\t" \
263 "ulw %[temp6], " #C "(%[" #P1 "]) \n\t" \
264 "ulw %[temp7], " #D "(%[" #P1 "]) \n\t" \
265 "addu %[temp4], %[temp4], %[temp0] \n\t" \
266 "addu %[temp5], %[temp5], %[temp1] \n\t" \
267 "addu %[temp6], %[temp6], %[temp2] \n\t" \
268 "addu %[temp7], %[temp7], %[temp3] \n\t" \
269 "addiu %[" #P0 "], %[" #P0 "], 16 \n\t" \
270 ".if " #E " == 1 \n\t" \
271 "addiu %[" #P1 "], %[" #P1 "], 16 \n\t" \
272 ".endif \n\t" \
273 "usw %[temp4], " #A "(%[" #P2 "]) \n\t" \
274 "usw %[temp5], " #B "(%[" #P2 "]) \n\t" \
275 "usw %[temp6], " #C "(%[" #P2 "]) \n\t" \
276 "usw %[temp7], " #D "(%[" #P2 "]) \n\t" \
277 "addiu %[" #P2 "], %[" #P2 "], 16 \n\t" \
278 "bne %[" #P0 "], %[LoopEnd], 1b \n\t" \
279 ".set pop \n\t" \
280
281 #define ASM_END_COMMON_0 \
282 : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1), \
283 [temp2]"=&r"(temp2), [temp3]"=&r"(temp3), \
284 [temp4]"=&r"(temp4), [temp5]"=&r"(temp5), \
285 [temp6]"=&r"(temp6), [temp7]"=&r"(temp7), \
286 [pa]"+r"(pa), [pout]"+r"(pout)
287
288 #define ASM_END_COMMON_1 \
289 : [LoopEnd]"r"(LoopEnd) \
290 : "memory", "at" \
291 );
292
293 #define ASM_END_0 \
294 ASM_END_COMMON_0 \
295 , [pb]"+r"(pb) \
296 ASM_END_COMMON_1
297
298 #define ASM_END_1 \
299 ASM_END_COMMON_0 \
300 ASM_END_COMMON_1
301
302 #define ADD_VECTOR(A, B, OUT, SIZE, EXTRA_SIZE) do { \
303 const uint32_t* pa = (const uint32_t*)(A); \
304 const uint32_t* pb = (const uint32_t*)(B); \
305 uint32_t* pout = (uint32_t*)(OUT); \
306 const uint32_t* const LoopEnd = pa + (SIZE); \
307 assert((SIZE) % 4 == 0); \
308 ASM_START \
309 ADD_TO_OUT(0, 4, 8, 12, 1, pa, pb, pout) \
310 ASM_END_0 \
311 if ((EXTRA_SIZE) > 0) { \
312 const int last = (EXTRA_SIZE); \
313 int i; \
314 for (i = 0; i < last; ++i) pout[i] = pa[i] + pb[i]; \
315 } \
316 } while (0)
317
318 #define ADD_VECTOR_EQ(A, OUT, SIZE, EXTRA_SIZE) do { \
319 const uint32_t* pa = (const uint32_t*)(A); \
320 uint32_t* pout = (uint32_t*)(OUT); \
321 const uint32_t* const LoopEnd = pa + (SIZE); \
322 assert((SIZE) % 4 == 0); \
323 ASM_START \
324 ADD_TO_OUT(0, 4, 8, 12, 0, pa, pout, pout) \
325 ASM_END_1 \
326 if ((EXTRA_SIZE) > 0) { \
327 const int last = (EXTRA_SIZE); \
328 int i; \
329 for (i = 0; i < last; ++i) pout[i] += pa[i]; \
330 } \
331 } while (0)
332
HistogramAdd(const VP8LHistogram * const a,const VP8LHistogram * const b,VP8LHistogram * const out)333 static void HistogramAdd(const VP8LHistogram* const a,
334 const VP8LHistogram* const b,
335 VP8LHistogram* const out) {
336 uint32_t temp0, temp1, temp2, temp3, temp4, temp5, temp6, temp7;
337 const int extra_cache_size = VP8LHistogramNumCodes(a->palette_code_bits_)
338 - (NUM_LITERAL_CODES + NUM_LENGTH_CODES);
339 assert(a->palette_code_bits_ == b->palette_code_bits_);
340
341 if (b != out) {
342 ADD_VECTOR(a->literal_, b->literal_, out->literal_,
343 NUM_LITERAL_CODES + NUM_LENGTH_CODES, extra_cache_size);
344 ADD_VECTOR(a->distance_, b->distance_, out->distance_,
345 NUM_DISTANCE_CODES, 0);
346 ADD_VECTOR(a->red_, b->red_, out->red_, NUM_LITERAL_CODES, 0);
347 ADD_VECTOR(a->blue_, b->blue_, out->blue_, NUM_LITERAL_CODES, 0);
348 ADD_VECTOR(a->alpha_, b->alpha_, out->alpha_, NUM_LITERAL_CODES, 0);
349 } else {
350 ADD_VECTOR_EQ(a->literal_, out->literal_,
351 NUM_LITERAL_CODES + NUM_LENGTH_CODES, extra_cache_size);
352 ADD_VECTOR_EQ(a->distance_, out->distance_, NUM_DISTANCE_CODES, 0);
353 ADD_VECTOR_EQ(a->red_, out->red_, NUM_LITERAL_CODES, 0);
354 ADD_VECTOR_EQ(a->blue_, out->blue_, NUM_LITERAL_CODES, 0);
355 ADD_VECTOR_EQ(a->alpha_, out->alpha_, NUM_LITERAL_CODES, 0);
356 }
357 }
358
359 #undef ADD_VECTOR_EQ
360 #undef ADD_VECTOR
361 #undef ASM_END_1
362 #undef ASM_END_0
363 #undef ASM_END_COMMON_1
364 #undef ASM_END_COMMON_0
365 #undef ADD_TO_OUT
366 #undef ASM_START
367
368 //------------------------------------------------------------------------------
369 // Entry point
370
371 extern void VP8LEncDspInitMIPS32(void);
372
VP8LEncDspInitMIPS32(void)373 WEBP_TSAN_IGNORE_FUNCTION void VP8LEncDspInitMIPS32(void) {
374 VP8LFastSLog2Slow = FastSLog2Slow;
375 VP8LFastLog2Slow = FastLog2Slow;
376 VP8LExtraCost = ExtraCost;
377 VP8LExtraCostCombined = ExtraCostCombined;
378 VP8LGetEntropyUnrefinedHelper = GetEntropyUnrefinedHelper;
379 VP8LHistogramAdd = HistogramAdd;
380 }
381
382 #else // !WEBP_USE_MIPS32
383
384 WEBP_DSP_INIT_STUB(VP8LEncDspInitMIPS32)
385
386 #endif // WEBP_USE_MIPS32
387