The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkPackBits.cpp

gfx/skia/trunk/src/core/SkPackBits.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:947abd402f01
1
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8 #include "SkPackBits.h"
9
10 #define GATHER_STATSx
11
12 static inline void small_memcpy(void* SK_RESTRICT dst,
13 const void* SK_RESTRICT src, int n) {
14 SkASSERT(n > 0 && n <= 15);
15 uint8_t* d = (uint8_t*)dst;
16 const uint8_t* s = (const uint8_t*)src;
17 switch (n) {
18 case 15: *d++ = *s++;
19 case 14: *d++ = *s++;
20 case 13: *d++ = *s++;
21 case 12: *d++ = *s++;
22 case 11: *d++ = *s++;
23 case 10: *d++ = *s++;
24 case 9: *d++ = *s++;
25 case 8: *d++ = *s++;
26 case 7: *d++ = *s++;
27 case 6: *d++ = *s++;
28 case 5: *d++ = *s++;
29 case 4: *d++ = *s++;
30 case 3: *d++ = *s++;
31 case 2: *d++ = *s++;
32 case 1: *d++ = *s++;
33 case 0: break;
34 }
35 }
36
37 static inline void small_memset(void* dst, uint8_t value, int n) {
38 SkASSERT(n > 0 && n <= 15);
39 uint8_t* d = (uint8_t*)dst;
40 switch (n) {
41 case 15: *d++ = value;
42 case 14: *d++ = value;
43 case 13: *d++ = value;
44 case 12: *d++ = value;
45 case 11: *d++ = value;
46 case 10: *d++ = value;
47 case 9: *d++ = value;
48 case 8: *d++ = value;
49 case 7: *d++ = value;
50 case 6: *d++ = value;
51 case 5: *d++ = value;
52 case 4: *d++ = value;
53 case 3: *d++ = value;
54 case 2: *d++ = value;
55 case 1: *d++ = value;
56 case 0: break;
57 }
58 }
59
60 // can we do better for small counts with our own inlined memcpy/memset?
61
62 #define PB_MEMSET(addr, value, count) \
63 do { \
64 if ((count) > 15) { \
65 memset(addr, value, count); \
66 } else { \
67 small_memset(addr, value, count); \
68 } \
69 } while (0)
70
71 #define PB_MEMCPY(dst, src, count) \
72 do { \
73 if ((count) > 15) { \
74 memcpy(dst, src, count); \
75 } else { \
76 small_memcpy(dst, src, count); \
77 } \
78 } while (0)
79
80 ///////////////////////////////////////////////////////////////////////////////
81
82 #ifdef GATHER_STATS
83 static int gMemSetBuckets[129];
84 static int gMemCpyBuckets[129];
85 static int gCounter;
86
87 static void register_memset_count(int n) {
88 SkASSERT((unsigned)n <= 128);
89 gMemSetBuckets[n] += 1;
90 gCounter += 1;
91
92 if ((gCounter & 0xFF) == 0) {
93 SkDebugf("----- packbits memset stats: ");
94 for (size_t i = 0; i < SK_ARRAY_COUNT(gMemSetBuckets); i++) {
95 if (gMemSetBuckets[i]) {
96 SkDebugf(" %d:%d", i, gMemSetBuckets[i]);
97 }
98 }
99 }
100 }
101 static void register_memcpy_count(int n) {
102 SkASSERT((unsigned)n <= 128);
103 gMemCpyBuckets[n] += 1;
104 gCounter += 1;
105
106 if ((gCounter & 0x1FF) == 0) {
107 SkDebugf("----- packbits memcpy stats: ");
108 for (size_t i = 0; i < SK_ARRAY_COUNT(gMemCpyBuckets); i++) {
109 if (gMemCpyBuckets[i]) {
110 SkDebugf(" %d:%d", i, gMemCpyBuckets[i]);
111 }
112 }
113 }
114 }
115 #else
116 #define register_memset_count(n)
117 #define register_memcpy_count(n)
118 #endif
119
120
121 ///////////////////////////////////////////////////////////////////////////////
122
123 size_t SkPackBits::ComputeMaxSize16(int count) {
124 // worst case is the number of 16bit values (times 2) +
125 // 1 byte per (up to) 128 entries.
126 return ((count + 127) >> 7) + (count << 1);
127 }
128
129 size_t SkPackBits::ComputeMaxSize8(int count) {
130 // worst case is the number of 8bit values + 1 byte per (up to) 128 entries.
131 return ((count + 127) >> 7) + count;
132 }
133
134 static uint8_t* flush_same16(uint8_t dst[], uint16_t value, int count) {
135 while (count > 0) {
136 int n = count;
137 if (n > 128) {
138 n = 128;
139 }
140 *dst++ = (uint8_t)(n - 1);
141 *dst++ = (uint8_t)(value >> 8);
142 *dst++ = (uint8_t)value;
143 count -= n;
144 }
145 return dst;
146 }
147
148 static uint8_t* flush_same8(uint8_t dst[], uint8_t value, int count) {
149 while (count > 0) {
150 int n = count;
151 if (n > 128) {
152 n = 128;
153 }
154 *dst++ = (uint8_t)(n - 1);
155 *dst++ = (uint8_t)value;
156 count -= n;
157 }
158 return dst;
159 }
160
161 static uint8_t* flush_diff16(uint8_t* SK_RESTRICT dst,
162 const uint16_t* SK_RESTRICT src, int count) {
163 while (count > 0) {
164 int n = count;
165 if (n > 128) {
166 n = 128;
167 }
168 *dst++ = (uint8_t)(n + 127);
169 PB_MEMCPY(dst, src, n * sizeof(uint16_t));
170 src += n;
171 dst += n * sizeof(uint16_t);
172 count -= n;
173 }
174 return dst;
175 }
176
177 static uint8_t* flush_diff8(uint8_t* SK_RESTRICT dst,
178 const uint8_t* SK_RESTRICT src, int count) {
179 while (count > 0) {
180 int n = count;
181 if (n > 128) {
182 n = 128;
183 }
184 *dst++ = (uint8_t)(n + 127);
185 PB_MEMCPY(dst, src, n);
186 src += n;
187 dst += n;
188 count -= n;
189 }
190 return dst;
191 }
192
193 size_t SkPackBits::Pack16(const uint16_t* SK_RESTRICT src, int count,
194 uint8_t* SK_RESTRICT dst) {
195 uint8_t* origDst = dst;
196 const uint16_t* stop = src + count;
197
198 for (;;) {
199 count = stop - src;
200 SkASSERT(count >= 0);
201 if (count == 0) {
202 return dst - origDst;
203 }
204 if (1 == count) {
205 *dst++ = 0;
206 *dst++ = (uint8_t)(*src >> 8);
207 *dst++ = (uint8_t)*src;
208 return dst - origDst;
209 }
210
211 unsigned value = *src;
212 const uint16_t* s = src + 1;
213
214 if (*s == value) { // accumulate same values...
215 do {
216 s++;
217 if (s == stop) {
218 break;
219 }
220 } while (*s == value);
221 dst = flush_same16(dst, value, s - src);
222 } else { // accumulate diff values...
223 do {
224 if (++s == stop) {
225 goto FLUSH_DIFF;
226 }
227 } while (*s != s[-1]);
228 s -= 1; // back up so we don't grab one of the "same" values that follow
229 FLUSH_DIFF:
230 dst = flush_diff16(dst, src, s - src);
231 }
232 src = s;
233 }
234 }
235
236 size_t SkPackBits::Pack8(const uint8_t* SK_RESTRICT src, int count,
237 uint8_t* SK_RESTRICT dst) {
238 uint8_t* origDst = dst;
239 const uint8_t* stop = src + count;
240
241 for (;;) {
242 count = stop - src;
243 SkASSERT(count >= 0);
244 if (count == 0) {
245 return dst - origDst;
246 }
247 if (1 == count) {
248 *dst++ = 0;
249 *dst++ = *src;
250 return dst - origDst;
251 }
252
253 unsigned value = *src;
254 const uint8_t* s = src + 1;
255
256 if (*s == value) { // accumulate same values...
257 do {
258 s++;
259 if (s == stop) {
260 break;
261 }
262 } while (*s == value);
263 dst = flush_same8(dst, value, s - src);
264 } else { // accumulate diff values...
265 do {
266 if (++s == stop) {
267 goto FLUSH_DIFF;
268 }
269 // only stop if we hit 3 in a row,
270 // otherwise we get bigger than compuatemax
271 } while (*s != s[-1] || s[-1] != s[-2]);
272 s -= 2; // back up so we don't grab the "same" values that follow
273 FLUSH_DIFF:
274 dst = flush_diff8(dst, src, s - src);
275 }
276 src = s;
277 }
278 }
279
280 #include "SkUtils.h"
281
282 int SkPackBits::Unpack16(const uint8_t* SK_RESTRICT src, size_t srcSize,
283 uint16_t* SK_RESTRICT dst) {
284 uint16_t* origDst = dst;
285 const uint8_t* stop = src + srcSize;
286
287 while (src < stop) {
288 unsigned n = *src++;
289 if (n <= 127) { // repeat count (n + 1)
290 n += 1;
291 sk_memset16(dst, (src[0] << 8) | src[1], n);
292 src += 2;
293 } else { // same count (n - 127)
294 n -= 127;
295 PB_MEMCPY(dst, src, n * sizeof(uint16_t));
296 src += n * sizeof(uint16_t);
297 }
298 dst += n;
299 }
300 SkASSERT(src == stop);
301 return dst - origDst;
302 }
303
304 int SkPackBits::Unpack8(const uint8_t* SK_RESTRICT src, size_t srcSize,
305 uint8_t* SK_RESTRICT dst) {
306 uint8_t* origDst = dst;
307 const uint8_t* stop = src + srcSize;
308
309 while (src < stop) {
310 unsigned n = *src++;
311 if (n <= 127) { // repeat count (n + 1)
312 n += 1;
313 PB_MEMSET(dst, *src++, n);
314 } else { // same count (n - 127)
315 n -= 127;
316 PB_MEMCPY(dst, src, n);
317 src += n;
318 }
319 dst += n;
320 }
321 SkASSERT(src == stop);
322 return dst - origDst;
323 }
324
325 enum UnpackState {
326 CLEAN_STATE,
327 REPEAT_BYTE_STATE,
328 COPY_SRC_STATE
329 };
330
331 void SkPackBits::Unpack8(uint8_t* SK_RESTRICT dst, size_t dstSkip,
332 size_t dstWrite, const uint8_t* SK_RESTRICT src) {
333 if (dstWrite == 0) {
334 return;
335 }
336
337 UnpackState state = CLEAN_STATE;
338 size_t stateCount = 0;
339
340 // state 1: do the skip-loop
341 while (dstSkip > 0) {
342 unsigned n = *src++;
343 if (n <= 127) { // repeat count (n + 1)
344 n += 1;
345 if (n > dstSkip) {
346 state = REPEAT_BYTE_STATE;
347 stateCount = n - dstSkip;
348 n = dstSkip;
349 // we don't increment src here, since its needed in stage 2
350 } else {
351 src++; // skip the src byte
352 }
353 } else { // same count (n - 127)
354 n -= 127;
355 if (n > dstSkip) {
356 state = COPY_SRC_STATE;
357 stateCount = n - dstSkip;
358 n = dstSkip;
359 }
360 src += n;
361 }
362 dstSkip -= n;
363 }
364
365 // stage 2: perform any catchup from the skip-stage
366 if (stateCount > dstWrite) {
367 stateCount = dstWrite;
368 }
369 switch (state) {
370 case REPEAT_BYTE_STATE:
371 SkASSERT(stateCount > 0);
372 register_memset_count(stateCount);
373 PB_MEMSET(dst, *src++, stateCount);
374 break;
375 case COPY_SRC_STATE:
376 SkASSERT(stateCount > 0);
377 register_memcpy_count(stateCount);
378 PB_MEMCPY(dst, src, stateCount);
379 src += stateCount;
380 break;
381 default:
382 SkASSERT(stateCount == 0);
383 break;
384 }
385 dst += stateCount;
386 dstWrite -= stateCount;
387
388 // copy at most dstWrite bytes into dst[]
389 while (dstWrite > 0) {
390 unsigned n = *src++;
391 if (n <= 127) { // repeat count (n + 1)
392 n += 1;
393 if (n > dstWrite) {
394 n = dstWrite;
395 }
396 register_memset_count(n);
397 PB_MEMSET(dst, *src++, n);
398 } else { // same count (n - 127)
399 n -= 127;
400 if (n > dstWrite) {
401 n = dstWrite;
402 }
403 register_memcpy_count(n);
404 PB_MEMCPY(dst, src, n);
405 src += n;
406 }
407 dst += n;
408 dstWrite -= n;
409 }
410 SkASSERT(0 == dstWrite);
411 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial