1/*
2 * Copyright 2015 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 "SkRWBuffer.h"
9#include "SkStream.h"
10
11// Force small chunks to be a page's worth
12static const size_t kMinAllocSize = 4096;
13
14struct SkBufferBlock {
15    SkBufferBlock*  fNext;
16    size_t          fUsed;
17    size_t          fCapacity;
18
19    const void* startData() const { return this + 1; };
20
21    size_t avail() const { return fCapacity - fUsed; }
22    void* availData() { return (char*)this->startData() + fUsed; }
23
24    static SkBufferBlock* Alloc(size_t length) {
25        size_t capacity = LengthToCapacity(length);
26        SkBufferBlock* block = (SkBufferBlock*)sk_malloc_throw(sizeof(SkBufferBlock) + capacity);
27        block->fNext = NULL;
28        block->fUsed = 0;
29        block->fCapacity = capacity;
30        return block;
31    }
32
33    // Return number of bytes actually appended
34    size_t append(const void* src, size_t length) {
35        this->validate();
36        size_t amount = SkTMin(this->avail(), length);
37        memcpy(this->availData(), src, amount);
38        fUsed += amount;
39        this->validate();
40        return amount;
41    }
42
43    void validate() const {
44#ifdef SK_DEBUG
45        SkASSERT(fCapacity > 0);
46        SkASSERT(fUsed <= fCapacity);
47#endif
48    }
49
50private:
51    static size_t LengthToCapacity(size_t length) {
52        const size_t minSize = kMinAllocSize - sizeof(SkBufferBlock);
53        return SkTMax(length, minSize);
54    }
55};
56
57struct SkBufferHead {
58    mutable int32_t fRefCnt;
59    SkBufferBlock   fBlock;
60
61    static size_t LengthToCapacity(size_t length) {
62        const size_t minSize = kMinAllocSize - sizeof(SkBufferHead);
63        return SkTMax(length, minSize);
64    }
65
66    static SkBufferHead* Alloc(size_t length) {
67        size_t capacity = LengthToCapacity(length);
68        size_t size = sizeof(SkBufferHead) + capacity;
69        SkBufferHead* head = (SkBufferHead*)sk_malloc_throw(size);
70        head->fRefCnt = 1;
71        head->fBlock.fNext = NULL;
72        head->fBlock.fUsed = 0;
73        head->fBlock.fCapacity = capacity;
74        return head;
75    }
76
77    void ref() const {
78        SkASSERT(fRefCnt > 0);
79        sk_atomic_inc(&fRefCnt);
80    }
81
82    void unref() const {
83        SkASSERT(fRefCnt > 0);
84        // A release here acts in place of all releases we "should" have been doing in ref().
85        if (1 == sk_atomic_fetch_add(&fRefCnt, -1, sk_memory_order_acq_rel)) {
86            // Like unique(), the acquire is only needed on success.
87            SkBufferBlock* block = fBlock.fNext;
88            sk_free((void*)this);
89            while (block) {
90                SkBufferBlock* next = block->fNext;
91                sk_free(block);
92                block = next;
93            }
94        }
95    }
96
97    void validate(size_t minUsed, SkBufferBlock* tail = NULL) const {
98#ifdef SK_DEBUG
99        SkASSERT(fRefCnt > 0);
100        size_t totalUsed = 0;
101        const SkBufferBlock* block = &fBlock;
102        const SkBufferBlock* lastBlock = block;
103        while (block) {
104            block->validate();
105            totalUsed += block->fUsed;
106            lastBlock = block;
107            block = block->fNext;
108        }
109        SkASSERT(minUsed <= totalUsed);
110        if (tail) {
111            SkASSERT(tail == lastBlock);
112        }
113#endif
114    }
115};
116
117SkROBuffer::SkROBuffer(const SkBufferHead* head, size_t used) : fHead(head), fUsed(used) {
118    if (head) {
119        fHead->ref();
120        SkASSERT(used > 0);
121        head->validate(used);
122    } else {
123        SkASSERT(0 == used);
124    }
125}
126
127SkROBuffer::~SkROBuffer() {
128    if (fHead) {
129        fHead->validate(fUsed);
130        fHead->unref();
131    }
132}
133
134SkROBuffer::Iter::Iter(const SkROBuffer* buffer) {
135    this->reset(buffer);
136}
137
138void SkROBuffer::Iter::reset(const SkROBuffer* buffer) {
139    if (buffer) {
140        fBlock = &buffer->fHead->fBlock;
141        fRemaining = buffer->fUsed;
142    } else {
143        fBlock = NULL;
144        fRemaining = 0;
145    }
146}
147
148const void* SkROBuffer::Iter::data() const {
149    return fRemaining ? fBlock->startData() : NULL;
150}
151
152size_t SkROBuffer::Iter::size() const {
153    return SkTMin(fBlock->fUsed, fRemaining);
154}
155
156bool SkROBuffer::Iter::next() {
157    if (fRemaining) {
158        fRemaining -= this->size();
159        fBlock = fBlock->fNext;
160    }
161    return fRemaining != 0;
162}
163
164SkRWBuffer::SkRWBuffer(size_t initialCapacity) : fHead(NULL), fTail(NULL), fTotalUsed(0) {}
165
166SkRWBuffer::~SkRWBuffer() {
167    this->validate();
168    fHead->unref();
169}
170
171void SkRWBuffer::append(const void* src, size_t length) {
172    this->validate();
173    if (0 == length) {
174        return;
175    }
176
177    fTotalUsed += length;
178
179    if (NULL == fHead) {
180        fHead = SkBufferHead::Alloc(length);
181        fTail = &fHead->fBlock;
182    }
183
184    size_t written = fTail->append(src, length);
185    SkASSERT(written <= length);
186    src = (const char*)src + written;
187    length -= written;
188
189    if (length) {
190        SkBufferBlock* block = SkBufferBlock::Alloc(length);
191        fTail->fNext = block;
192        fTail = block;
193        written = fTail->append(src, length);
194        SkASSERT(written == length);
195    }
196    this->validate();
197}
198
199void* SkRWBuffer::append(size_t length) {
200    this->validate();
201    if (0 == length) {
202        return NULL;
203    }
204
205    fTotalUsed += length;
206
207    if (NULL == fHead) {
208        fHead = SkBufferHead::Alloc(length);
209        fTail = &fHead->fBlock;
210    } else if (fTail->avail() < length) {
211        SkBufferBlock* block = SkBufferBlock::Alloc(length);
212        fTail->fNext = block;
213        fTail = block;
214    }
215
216    fTail->fUsed += length;
217    this->validate();
218    return (char*)fTail->availData() - length;
219}
220
221#ifdef SK_DEBUG
222void SkRWBuffer::validate() const {
223    if (fHead) {
224        fHead->validate(fTotalUsed, fTail);
225    } else {
226        SkASSERT(NULL == fTail);
227        SkASSERT(0 == fTotalUsed);
228    }
229}
230#endif
231
232SkROBuffer* SkRWBuffer::newRBufferSnapshot() const {
233    return SkNEW_ARGS(SkROBuffer, (fHead, fTotalUsed));
234}
235
236///////////////////////////////////////////////////////////////////////////////////////////////////
237
238class SkROBufferStreamAsset : public SkStreamAsset {
239    void validate() const {
240#ifdef SK_DEBUG
241        SkASSERT(fGlobalOffset <= fBuffer->size());
242        SkASSERT(fLocalOffset <= fIter.size());
243        SkASSERT(fLocalOffset <= fGlobalOffset);
244#endif
245    }
246
247#ifdef SK_DEBUG
248    class AutoValidate {
249        SkROBufferStreamAsset* fStream;
250    public:
251        AutoValidate(SkROBufferStreamAsset* stream) : fStream(stream) { stream->validate(); }
252        ~AutoValidate() { fStream->validate(); }
253    };
254    #define AUTO_VALIDATE   AutoValidate av(this);
255#else
256    #define AUTO_VALIDATE
257#endif
258
259public:
260    SkROBufferStreamAsset(const SkROBuffer* buffer) : fBuffer(SkRef(buffer)), fIter(buffer) {
261        fGlobalOffset = fLocalOffset = 0;
262    }
263
264    virtual ~SkROBufferStreamAsset() { fBuffer->unref(); }
265
266    size_t getLength() const override { return fBuffer->size(); }
267
268    bool rewind() override {
269        AUTO_VALIDATE
270        fIter.reset(fBuffer);
271        fGlobalOffset = fLocalOffset = 0;
272        return true;
273    }
274
275    size_t read(void* dst, size_t request) override {
276        AUTO_VALIDATE
277        size_t bytesRead = 0;
278        for (;;) {
279            size_t size = fIter.size();
280            SkASSERT(fLocalOffset <= size);
281            size_t avail = SkTMin(size - fLocalOffset, request - bytesRead);
282            if (dst) {
283                memcpy(dst, (const char*)fIter.data() + fLocalOffset, avail);
284                dst = (char*)dst + avail;
285            }
286            bytesRead += avail;
287            fLocalOffset += avail;
288            SkASSERT(bytesRead <= request);
289            if (bytesRead == request) {
290                break;
291            }
292            // If we get here, we've exhausted the current iter
293            SkASSERT(fLocalOffset == size);
294            fLocalOffset = 0;
295            if (!fIter.next()) {
296                break;   // ran out of data
297            }
298        }
299        fGlobalOffset += bytesRead;
300        SkASSERT(fGlobalOffset <= fBuffer->size());
301        return bytesRead;
302    }
303
304    bool isAtEnd() const override {
305        return fBuffer->size() == fGlobalOffset;
306    }
307
308    SkStreamAsset* duplicate() const override {
309        return SkNEW_ARGS(SkROBufferStreamAsset, (fBuffer));
310    }
311
312    size_t getPosition() const {
313        return fGlobalOffset;
314    }
315
316    bool seek(size_t position) {
317        AUTO_VALIDATE
318        if (position < fGlobalOffset) {
319            this->rewind();
320        }
321        (void)this->skip(position - fGlobalOffset);
322        return true;
323    }
324
325    bool move(long offset) {
326        AUTO_VALIDATE
327        offset += fGlobalOffset;
328        if (offset <= 0) {
329            this->rewind();
330        } else {
331            (void)this->seek(SkToSizeT(offset));
332        }
333        return true;
334    }
335
336    SkStreamAsset* fork() const override {
337        SkStreamAsset* clone = this->duplicate();
338        clone->seek(this->getPosition());
339        return clone;
340    }
341
342
343private:
344    const SkROBuffer*   fBuffer;
345    SkROBuffer::Iter    fIter;
346    size_t              fLocalOffset;
347    size_t              fGlobalOffset;
348};
349
350SkStreamAsset* SkRWBuffer::newStreamSnapshot() const {
351    SkAutoTUnref<SkROBuffer> buffer(this->newRBufferSnapshot());
352    return SkNEW_ARGS(SkROBufferStreamAsset, (buffer));
353}
354