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