1 /*
2  * Copyright 2011 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #include "SkPackBits.h"
9 #include "SkTo.h"
10 
11 #include <cstring>
12 
13 size_t SkPackBits::ComputeMaxSize8(size_t srcSize) {
14     // worst case is the number of 8bit values + 1 byte per (up to) 128 entries.
15     return ((srcSize + 127) >> 7) + srcSize;
16 }
17 
18 static uint8_t* flush_same8(uint8_t dst[], uint8_t value, size_t count) {
19     while (count > 0) {
20         size_t n = count > 128 ? 128 : count;
21         *dst++ = (uint8_t)(n - 1);
22         *dst++ = (uint8_t)value;
23         count -= n;
24     }
25     return dst;
26 }
27 
28 static uint8_t* flush_diff8(uint8_t* SK_RESTRICT dst,
29                             const uint8_t* SK_RESTRICT src, size_t count) {
30     while (count > 0) {
31         size_t n = count > 128 ? 128 : count;
32         *dst++ = (uint8_t)(n + 127);
33         memcpy(dst, src, n);
34         src += n;
35         dst += n;
36         count -= n;
37     }
38     return dst;
39 }
40 
41 size_t SkPackBits::Pack8(const uint8_t* SK_RESTRICT src, size_t srcSize,
42                          uint8_t* SK_RESTRICT dst, size_t dstSize) {
43     if (dstSize < ComputeMaxSize8(srcSize)) {
44         return 0;
45     }
46 
47     uint8_t* const origDst = dst;
48     const uint8_t* stop = src + srcSize;
49 
50     for (intptr_t count = stop - src; count > 0; count = stop - src) {
51         if (1 == count) {
52             *dst++ = 0;
53             *dst++ = *src;
54             break;
55         }
56 
57         unsigned value = *src;
58         const uint8_t* s = src + 1;
59 
60         if (*s == value) { // accumulate same values...
61             do {
62                 s++;
63                 if (s == stop) {
64                     break;
65                 }
66             } while (*s == value);
67             dst = flush_same8(dst, value, SkToInt(s - src));
68         } else {    // accumulate diff values...
69             do {
70                 if (++s == stop) {
71                     goto FLUSH_DIFF;
72                 }
73                 // only stop if we hit 3 in a row,
74                 // otherwise we get bigger than compuatemax
75             } while (*s != s[-1] || s[-1] != s[-2]);
76             s -= 2; // back up so we don't grab the "same" values that follow
77         FLUSH_DIFF:
78             dst = flush_diff8(dst, src, SkToInt(s - src));
79         }
80         src = s;
81     }
82     return dst - origDst;
83 }
84 
85 int SkPackBits::Unpack8(const uint8_t* SK_RESTRICT src, size_t srcSize,
86                         uint8_t* SK_RESTRICT dst, size_t dstSize) {
87     uint8_t* const origDst = dst;
88     uint8_t* const endDst = dst + dstSize;
89     const uint8_t* stop = src + srcSize;
90 
91     while (src < stop) {
92         unsigned n = *src++;
93         if (n <= 127) {   // repeat count (n + 1)
94             n += 1;
95             if (dst > (endDst - n) || src >= stop) {
96                 return 0;
97             }
98             memset(dst, *src++, n);
99         } else {    // same count (n - 127)
100             n -= 127;
101             if (dst > (endDst - n) || src > (stop - n)) {
102                 return 0;
103             }
104             memcpy(dst, src, n);
105             src += n;
106         }
107         dst += n;
108     }
109     SkASSERT(src <= stop);
110     SkASSERT(dst <= endDst);
111     return SkToInt(dst - origDst);
112 }
113