OLD | NEW |
1 | |
2 /* | 1 /* |
3 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
4 * | 3 * |
5 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 5 * found in the LICENSE file. |
7 */ | 6 */ |
8 #include "SkPackBits.h" | 7 #include "SkPackBits.h" |
9 | 8 |
10 #define GATHER_STATSx | |
11 | |
12 static inline void small_memcpy(void* SK_RESTRICT dst, | |
13 const void* SK_RESTRICT src, size_t 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, size_t 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) { | 9 size_t SkPackBits::ComputeMaxSize8(int count) { |
130 // worst case is the number of 8bit values + 1 byte per (up to) 128 entries. | 10 // worst case is the number of 8bit values + 1 byte per (up to) 128 entries. |
131 return ((count + 127) >> 7) + count; | 11 return ((count + 127) >> 7) + count; |
132 } | 12 } |
133 | 13 |
134 static uint8_t* flush_same16(uint8_t dst[], uint16_t value, int count) { | 14 static uint8_t* flush_same8(uint8_t dst[], uint8_t value, size_t count) { |
135 while (count > 0) { | 15 while (count > 0) { |
136 int n = count; | 16 int n = count > 128 ? 128 : 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); | 17 *dst++ = (uint8_t)(n - 1); |
155 *dst++ = (uint8_t)value; | 18 *dst++ = (uint8_t)value; |
156 count -= n; | 19 count -= n; |
157 } | 20 } |
158 return dst; | 21 return dst; |
159 } | 22 } |
160 | 23 |
161 static uint8_t* flush_diff16(uint8_t* SK_RESTRICT dst, | 24 static uint8_t* flush_diff8(uint8_t* SK_RESTRICT dst, |
162 const uint16_t* SK_RESTRICT src, int count) { | 25 const uint8_t* SK_RESTRICT src, size_t count) { |
163 while (count > 0) { | 26 while (count > 0) { |
164 int n = count; | 27 int n = count > 128 ? 128 : count; |
165 if (n > 128) { | |
166 n = 128; | |
167 } | |
168 *dst++ = (uint8_t)(n + 127); | 28 *dst++ = (uint8_t)(n + 127); |
169 PB_MEMCPY(dst, src, n * sizeof(uint16_t)); | 29 memcpy(dst, src, n); |
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; | 30 src += n; |
187 dst += n; | 31 dst += n; |
188 count -= n; | 32 count -= n; |
189 } | 33 } |
190 return dst; | 34 return dst; |
191 } | 35 } |
192 | 36 |
193 size_t SkPackBits::Pack16(const uint16_t* SK_RESTRICT src, int count, | 37 size_t SkPackBits::Pack8(const uint8_t* SK_RESTRICT src, size_t srcSize, |
194 uint8_t* SK_RESTRICT dst) { | 38 uint8_t* SK_RESTRICT dst, size_t dstSize) { |
195 uint8_t* origDst = dst; | 39 if (dstSize < ComputeMaxSize8(srcSize)) { |
196 const uint16_t* stop = src + count; | 40 return 0; |
| 41 } |
197 | 42 |
198 for (;;) { | 43 uint8_t* const origDst = dst; |
199 count = SkToInt(stop - src); | 44 const uint8_t* stop = src + srcSize; |
200 SkASSERT(count >= 0); | 45 |
201 if (count == 0) { | 46 for (intptr_t count = stop - src; count > 0; count = stop - src) { |
202 return dst - origDst; | |
203 } | |
204 if (1 == count) { | 47 if (1 == count) { |
205 *dst++ = 0; | 48 *dst++ = 0; |
206 *dst++ = (uint8_t)(*src >> 8); | 49 *dst++ = *src; |
207 *dst++ = (uint8_t)*src; | 50 break; |
208 return dst - origDst; | |
209 } | 51 } |
210 | 52 |
211 unsigned value = *src; | 53 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, SkToInt(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 fo
llow | |
229 FLUSH_DIFF: | |
230 dst = flush_diff16(dst, src, SkToInt(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 = SkToInt(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; | 54 const uint8_t* s = src + 1; |
255 | 55 |
256 if (*s == value) { // accumulate same values... | 56 if (*s == value) { // accumulate same values... |
257 do { | 57 do { |
258 s++; | 58 s++; |
259 if (s == stop) { | 59 if (s == stop) { |
260 break; | 60 break; |
261 } | 61 } |
262 } while (*s == value); | 62 } while (*s == value); |
263 dst = flush_same8(dst, value, SkToInt(s - src)); | 63 dst = flush_same8(dst, value, SkToInt(s - src)); |
264 } else { // accumulate diff values... | 64 } else { // accumulate diff values... |
265 do { | 65 do { |
266 if (++s == stop) { | 66 if (++s == stop) { |
267 goto FLUSH_DIFF; | 67 goto FLUSH_DIFF; |
268 } | 68 } |
269 // only stop if we hit 3 in a row, | 69 // only stop if we hit 3 in a row, |
270 // otherwise we get bigger than compuatemax | 70 // otherwise we get bigger than compuatemax |
271 } while (*s != s[-1] || s[-1] != s[-2]); | 71 } while (*s != s[-1] || s[-1] != s[-2]); |
272 s -= 2; // back up so we don't grab the "same" values that follow | 72 s -= 2; // back up so we don't grab the "same" values that follow |
273 FLUSH_DIFF: | 73 FLUSH_DIFF: |
274 dst = flush_diff8(dst, src, SkToInt(s - src)); | 74 dst = flush_diff8(dst, src, SkToInt(s - src)); |
275 } | 75 } |
276 src = s; | 76 src = s; |
277 } | 77 } |
| 78 return dst - origDst; |
278 } | 79 } |
279 | 80 |
280 #include "SkUtils.h" | 81 #include "SkUtils.h" |
281 | 82 |
282 int SkPackBits::Unpack16(const uint8_t* SK_RESTRICT src, size_t srcSize, | 83 int SkPackBits::Unpack8(const uint8_t* SK_RESTRICT src, size_t srcSize, |
283 uint16_t* SK_RESTRICT dst) { | 84 uint8_t* SK_RESTRICT dst, size_t dstSize) { |
284 uint16_t* origDst = dst; | 85 uint8_t* const origDst = dst; |
| 86 uint8_t* const endDst = dst + dstSize; |
285 const uint8_t* stop = src + srcSize; | 87 const uint8_t* stop = src + srcSize; |
286 | 88 |
287 while (src < stop) { | 89 while (src < stop) { |
288 unsigned n = *src++; | 90 unsigned n = *src++; |
289 if (n <= 127) { // repeat count (n + 1) | 91 if (n <= 127) { // repeat count (n + 1) |
290 n += 1; | 92 n += 1; |
291 sk_memset16(dst, (src[0] << 8) | src[1], n); | 93 if (dst >(endDst - n)) { |
292 src += 2; | 94 return 0; |
| 95 } |
| 96 memset(dst, *src++, n); |
293 } else { // same count (n - 127) | 97 } else { // same count (n - 127) |
294 n -= 127; | 98 n -= 127; |
295 PB_MEMCPY(dst, src, n * sizeof(uint16_t)); | 99 if (dst > (endDst - n)) { |
296 src += n * sizeof(uint16_t); | 100 return 0; |
297 } | 101 } |
298 dst += n; | 102 memcpy(dst, src, n); |
299 } | |
300 SkASSERT(src == stop); | |
301 return SkToInt(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; | 103 src += n; |
318 } | 104 } |
319 dst += n; | 105 dst += n; |
320 } | 106 } |
321 SkASSERT(src == stop); | 107 SkASSERT(src <= stop); |
322 return SkToInt(dst - origDst); | 108 return SkToInt(dst - origDst); |
323 } | 109 } |
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 size_t 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 size_t 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 } | |
OLD | NEW |