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