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
12static 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
37static 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)       \
63do {                                        \
64if ((count) > 15) {                     \
65memset(addr, value, count);         \
66} else {                                \
67small_memset(addr, value, count);   \
68}                                       \
69} while (0)
70
71#define PB_MEMCPY(dst, src, count)      \
72do {                                    \
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
87static 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}
101static 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
123size_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
129size_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
134static 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
148static 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
161static 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
177static 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
193size_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 = SkToInt(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, 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 follow
229        FLUSH_DIFF:
230            dst = flush_diff16(dst, src, SkToInt(s - src));
231        }
232        src = s;
233    }
234}
235
236size_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;
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, SkToInt(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, SkToInt(s - src));
275        }
276        src = s;
277    }
278}
279
280#include "SkUtils.h"
281
282int 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 SkToInt(dst - origDst);
302}
303
304int 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 SkToInt(dst - origDst);
323}
324
325enum UnpackState {
326    CLEAN_STATE,
327    REPEAT_BYTE_STATE,
328    COPY_SRC_STATE
329};
330
331void 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}
412