1
2/*
3 * Copyright 2006 The Android Open Source Project
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
9
10#include "SkString.h"
11#include "SkFixed.h"
12#include "SkThread.h"
13#include "SkUtils.h"
14#include <stdarg.h>
15#include <stdio.h>
16
17// number of bytes (on the stack) to receive the printf result
18static const size_t kBufferSize = 1024;
19
20#ifdef SK_BUILD_FOR_WIN
21    #define VSNPRINTF(buffer, size, format, args) \
22        _vsnprintf_s(buffer, size, _TRUNCATE, format, args)
23    #define SNPRINTF    _snprintf
24#else
25    #define VSNPRINTF   vsnprintf
26    #define SNPRINTF    snprintf
27#endif
28
29#define ARGS_TO_BUFFER(format, buffer, size)        \
30    do {                                            \
31        va_list args;                               \
32        va_start(args, format);                     \
33        VSNPRINTF(buffer, size, format, args);      \
34        va_end(args);                               \
35    } while (0)
36
37///////////////////////////////////////////////////////////////////////////////
38
39bool SkStrEndsWith(const char string[], const char suffixStr[]) {
40    SkASSERT(string);
41    SkASSERT(suffixStr);
42    size_t  strLen = strlen(string);
43    size_t  suffixLen = strlen(suffixStr);
44    return  strLen >= suffixLen &&
45            !strncmp(string + strLen - suffixLen, suffixStr, suffixLen);
46}
47
48bool SkStrEndsWith(const char string[], const char suffixChar) {
49    SkASSERT(string);
50    size_t  strLen = strlen(string);
51    if (0 == strLen) {
52        return false;
53    } else {
54        return (suffixChar == string[strLen-1]);
55    }
56}
57
58int SkStrStartsWithOneOf(const char string[], const char prefixes[]) {
59    int index = 0;
60    do {
61        const char* limit = strchr(prefixes, '\0');
62        if (!strncmp(string, prefixes, limit - prefixes)) {
63            return index;
64        }
65        prefixes = limit + 1;
66        index++;
67    } while (prefixes[0]);
68    return -1;
69}
70
71char* SkStrAppendU32(char string[], uint32_t dec) {
72    SkDEBUGCODE(char* start = string;)
73
74    char    buffer[SkStrAppendU32_MaxSize];
75    char*   p = buffer + sizeof(buffer);
76
77    do {
78        *--p = SkToU8('0' + dec % 10);
79        dec /= 10;
80    } while (dec != 0);
81
82    SkASSERT(p >= buffer);
83    char* stop = buffer + sizeof(buffer);
84    while (p < stop) {
85        *string++ = *p++;
86    }
87    SkASSERT(string - start <= SkStrAppendU32_MaxSize);
88    return string;
89}
90
91char* SkStrAppendS32(char string[], int32_t dec) {
92    if (dec < 0) {
93        *string++ = '-';
94        dec = -dec;
95    }
96    return SkStrAppendU32(string, static_cast<uint32_t>(dec));
97}
98
99char* SkStrAppendU64(char string[], uint64_t dec, int minDigits) {
100    SkDEBUGCODE(char* start = string;)
101
102    char    buffer[SkStrAppendU64_MaxSize];
103    char*   p = buffer + sizeof(buffer);
104
105    do {
106        *--p = SkToU8('0' + (int32_t) (dec % 10));
107        dec /= 10;
108        minDigits--;
109    } while (dec != 0);
110
111    while (minDigits > 0) {
112        *--p = '0';
113        minDigits--;
114    }
115
116    SkASSERT(p >= buffer);
117    size_t cp_len = buffer + sizeof(buffer) - p;
118    memcpy(string, p, cp_len);
119    string += cp_len;
120
121    SkASSERT(string - start <= SkStrAppendU64_MaxSize);
122    return string;
123}
124
125char* SkStrAppendS64(char string[], int64_t dec, int minDigits) {
126    if (dec < 0) {
127        *string++ = '-';
128        dec = -dec;
129    }
130    return SkStrAppendU64(string, static_cast<uint64_t>(dec), minDigits);
131}
132
133char* SkStrAppendFloat(char string[], float value) {
134    // since floats have at most 8 significant digits, we limit our %g to that.
135    static const char gFormat[] = "%.8g";
136    // make it 1 larger for the terminating 0
137    char buffer[SkStrAppendScalar_MaxSize + 1];
138    int len = SNPRINTF(buffer, sizeof(buffer), gFormat, value);
139    memcpy(string, buffer, len);
140    SkASSERT(len <= SkStrAppendScalar_MaxSize);
141    return string + len;
142}
143
144char* SkStrAppendFixed(char string[], SkFixed x) {
145    SkDEBUGCODE(char* start = string;)
146    if (x < 0) {
147        *string++ = '-';
148        x = -x;
149    }
150
151    unsigned frac = x & 0xFFFF;
152    x >>= 16;
153    if (frac == 0xFFFF) {
154        // need to do this to "round up", since 65535/65536 is closer to 1 than to .9999
155        x += 1;
156        frac = 0;
157    }
158    string = SkStrAppendS32(string, x);
159
160    // now handle the fractional part (if any)
161    if (frac) {
162        static const uint16_t   gTens[] = { 1000, 100, 10, 1 };
163        const uint16_t*         tens = gTens;
164
165        x = SkFixedRoundToInt(frac * 10000);
166        SkASSERT(x <= 10000);
167        if (x == 10000) {
168            x -= 1;
169        }
170        *string++ = '.';
171        do {
172            unsigned powerOfTen = *tens++;
173            *string++ = SkToU8('0' + x / powerOfTen);
174            x %= powerOfTen;
175        } while (x != 0);
176    }
177
178    SkASSERT(string - start <= SkStrAppendScalar_MaxSize);
179    return string;
180}
181
182///////////////////////////////////////////////////////////////////////////////
183
184// the 3 values are [length] [refcnt] [terminating zero data]
185const SkString::Rec SkString::gEmptyRec = { 0, 0, 0 };
186
187#define SizeOfRec()     (gEmptyRec.data() - (const char*)&gEmptyRec)
188
189static uint32_t trim_size_t_to_u32(size_t value) {
190    if (sizeof(size_t) > sizeof(uint32_t)) {
191        if (value > SK_MaxU32) {
192            value = SK_MaxU32;
193        }
194    }
195    return (uint32_t)value;
196}
197
198static size_t check_add32(size_t base, size_t extra) {
199    SkASSERT(base <= SK_MaxU32);
200    if (sizeof(size_t) > sizeof(uint32_t)) {
201        if (base + extra > SK_MaxU32) {
202            extra = SK_MaxU32 - base;
203        }
204    }
205    return extra;
206}
207
208SkString::Rec* SkString::AllocRec(const char text[], size_t len) {
209    Rec* rec;
210
211    if (0 == len) {
212        rec = const_cast<Rec*>(&gEmptyRec);
213    } else {
214        len = trim_size_t_to_u32(len);
215
216        // add 1 for terminating 0, then align4 so we can have some slop when growing the string
217        rec = (Rec*)sk_malloc_throw(SizeOfRec() + SkAlign4(len + 1));
218        rec->fLength = SkToU32(len);
219        rec->fRefCnt = 1;
220        if (text) {
221            memcpy(rec->data(), text, len);
222        }
223        rec->data()[len] = 0;
224    }
225    return rec;
226}
227
228SkString::Rec* SkString::RefRec(Rec* src) {
229    if (src != &gEmptyRec) {
230        sk_atomic_inc(&src->fRefCnt);
231    }
232    return src;
233}
234
235#ifdef SK_DEBUG
236void SkString::validate() const {
237    // make sure know one has written over our global
238    SkASSERT(0 == gEmptyRec.fLength);
239    SkASSERT(0 == gEmptyRec.fRefCnt);
240    SkASSERT(0 == gEmptyRec.data()[0]);
241
242    if (fRec != &gEmptyRec) {
243        SkASSERT(fRec->fLength > 0);
244        SkASSERT(fRec->fRefCnt > 0);
245        SkASSERT(0 == fRec->data()[fRec->fLength]);
246    }
247    SkASSERT(fStr == c_str());
248}
249#endif
250
251///////////////////////////////////////////////////////////////////////////////
252
253SkString::SkString() : fRec(const_cast<Rec*>(&gEmptyRec)) {
254#ifdef SK_DEBUG
255    fStr = fRec->data();
256#endif
257}
258
259SkString::SkString(size_t len) {
260    fRec = AllocRec(NULL, len);
261#ifdef SK_DEBUG
262    fStr = fRec->data();
263#endif
264}
265
266SkString::SkString(const char text[]) {
267    size_t  len = text ? strlen(text) : 0;
268
269    fRec = AllocRec(text, len);
270#ifdef SK_DEBUG
271    fStr = fRec->data();
272#endif
273}
274
275SkString::SkString(const char text[], size_t len) {
276    fRec = AllocRec(text, len);
277#ifdef SK_DEBUG
278    fStr = fRec->data();
279#endif
280}
281
282SkString::SkString(const SkString& src) {
283    src.validate();
284
285    fRec = RefRec(src.fRec);
286#ifdef SK_DEBUG
287    fStr = fRec->data();
288#endif
289}
290
291SkString::~SkString() {
292    this->validate();
293
294    if (fRec->fLength) {
295        SkASSERT(fRec->fRefCnt > 0);
296        if (sk_atomic_dec(&fRec->fRefCnt) == 1) {
297            sk_free(fRec);
298        }
299    }
300}
301
302bool SkString::equals(const SkString& src) const {
303    return fRec == src.fRec || this->equals(src.c_str(), src.size());
304}
305
306bool SkString::equals(const char text[]) const {
307    return this->equals(text, text ? strlen(text) : 0);
308}
309
310bool SkString::equals(const char text[], size_t len) const {
311    SkASSERT(len == 0 || text != NULL);
312
313    return fRec->fLength == len && !memcmp(fRec->data(), text, len);
314}
315
316SkString& SkString::operator=(const SkString& src) {
317    this->validate();
318
319    if (fRec != src.fRec) {
320        SkString    tmp(src);
321        this->swap(tmp);
322    }
323    return *this;
324}
325
326SkString& SkString::operator=(const char text[]) {
327    this->validate();
328
329    SkString tmp(text);
330    this->swap(tmp);
331
332    return *this;
333}
334
335void SkString::reset() {
336    this->validate();
337
338    if (fRec->fLength) {
339        SkASSERT(fRec->fRefCnt > 0);
340        if (sk_atomic_dec(&fRec->fRefCnt) == 1) {
341            sk_free(fRec);
342        }
343    }
344
345    fRec = const_cast<Rec*>(&gEmptyRec);
346#ifdef SK_DEBUG
347    fStr = fRec->data();
348#endif
349}
350
351char* SkString::writable_str() {
352    this->validate();
353
354    if (fRec->fLength) {
355        if (fRec->fRefCnt > 1) {
356            Rec* rec = AllocRec(fRec->data(), fRec->fLength);
357            if (sk_atomic_dec(&fRec->fRefCnt) == 1) {
358                // In this case after our check of fRecCnt > 1, we suddenly
359                // did become the only owner, so now we have two copies of the
360                // data (fRec and rec), so we need to delete one of them.
361                sk_free(fRec);
362            }
363            fRec = rec;
364        #ifdef SK_DEBUG
365            fStr = fRec->data();
366        #endif
367        }
368    }
369    return fRec->data();
370}
371
372void SkString::set(const char text[]) {
373    this->set(text, text ? strlen(text) : 0);
374}
375
376void SkString::set(const char text[], size_t len) {
377    len = trim_size_t_to_u32(len);
378
379    if (0 == len) {
380        this->reset();
381    } else if (1 == fRec->fRefCnt && len <= fRec->fLength) {
382        // should we resize if len <<<< fLength, to save RAM? (e.g. len < (fLength>>1))?
383        // just use less of the buffer without allocating a smaller one
384        char* p = this->writable_str();
385        if (text) {
386            memcpy(p, text, len);
387        }
388        p[len] = 0;
389        fRec->fLength = SkToU32(len);
390    } else if (1 == fRec->fRefCnt && (fRec->fLength >> 2) == (len >> 2)) {
391        // we have spare room in the current allocation, so don't alloc a larger one
392        char* p = this->writable_str();
393        if (text) {
394            memcpy(p, text, len);
395        }
396        p[len] = 0;
397        fRec->fLength = SkToU32(len);
398    } else {
399        SkString tmp(text, len);
400        this->swap(tmp);
401    }
402}
403
404void SkString::setUTF16(const uint16_t src[]) {
405    int count = 0;
406
407    while (src[count]) {
408        count += 1;
409    }
410    this->setUTF16(src, count);
411}
412
413void SkString::setUTF16(const uint16_t src[], size_t count) {
414    count = trim_size_t_to_u32(count);
415
416    if (0 == count) {
417        this->reset();
418    } else if (count <= fRec->fLength) {
419        // should we resize if len <<<< fLength, to save RAM? (e.g. len < (fLength>>1))
420        if (count < fRec->fLength) {
421            this->resize(count);
422        }
423        char* p = this->writable_str();
424        for (size_t i = 0; i < count; i++) {
425            p[i] = SkToU8(src[i]);
426        }
427        p[count] = 0;
428    } else {
429        SkString tmp(count); // puts a null terminator at the end of the string
430        char*    p = tmp.writable_str();
431
432        for (size_t i = 0; i < count; i++) {
433            p[i] = SkToU8(src[i]);
434        }
435        this->swap(tmp);
436    }
437}
438
439void SkString::insert(size_t offset, const char text[]) {
440    this->insert(offset, text, text ? strlen(text) : 0);
441}
442
443void SkString::insert(size_t offset, const char text[], size_t len) {
444    if (len) {
445        size_t length = fRec->fLength;
446        if (offset > length) {
447            offset = length;
448        }
449
450        // Check if length + len exceeds 32bits, we trim len
451        len = check_add32(length, len);
452        if (0 == len) {
453            return;
454        }
455
456        /*  If we're the only owner, and we have room in our allocation for the insert,
457            do it in place, rather than allocating a new buffer.
458
459            To know we have room, compare the allocated sizes
460            beforeAlloc = SkAlign4(length + 1)
461            afterAlloc  = SkAligh4(length + 1 + len)
462            but SkAlign4(x) is (x + 3) >> 2 << 2
463            which is equivalent for testing to (length + 1 + 3) >> 2 == (length + 1 + 3 + len) >> 2
464            and we can then eliminate the +1+3 since that doesn't affec the answer
465        */
466        if (1 == fRec->fRefCnt && (length >> 2) == ((length + len) >> 2)) {
467            char* dst = this->writable_str();
468
469            if (offset < length) {
470                memmove(dst + offset + len, dst + offset, length - offset);
471            }
472            memcpy(dst + offset, text, len);
473
474            dst[length + len] = 0;
475            fRec->fLength = SkToU32(length + len);
476        } else {
477            /*  Seems we should use realloc here, since that is safe if it fails
478                (we have the original data), and might be faster than alloc/copy/free.
479            */
480            SkString    tmp(fRec->fLength + len);
481            char*       dst = tmp.writable_str();
482
483            if (offset > 0) {
484                memcpy(dst, fRec->data(), offset);
485            }
486            memcpy(dst + offset, text, len);
487            if (offset < fRec->fLength) {
488                memcpy(dst + offset + len, fRec->data() + offset,
489                       fRec->fLength - offset);
490            }
491
492            this->swap(tmp);
493        }
494    }
495}
496
497void SkString::insertUnichar(size_t offset, SkUnichar uni) {
498    char    buffer[kMaxBytesInUTF8Sequence];
499    size_t  len = SkUTF8_FromUnichar(uni, buffer);
500
501    if (len) {
502        this->insert(offset, buffer, len);
503    }
504}
505
506void SkString::insertS32(size_t offset, int32_t dec) {
507    char    buffer[SkStrAppendS32_MaxSize];
508    char*   stop = SkStrAppendS32(buffer, dec);
509    this->insert(offset, buffer, stop - buffer);
510}
511
512void SkString::insertS64(size_t offset, int64_t dec, int minDigits) {
513    char    buffer[SkStrAppendS64_MaxSize];
514    char*   stop = SkStrAppendS64(buffer, dec, minDigits);
515    this->insert(offset, buffer, stop - buffer);
516}
517
518void SkString::insertU32(size_t offset, uint32_t dec) {
519    char    buffer[SkStrAppendU32_MaxSize];
520    char*   stop = SkStrAppendU32(buffer, dec);
521    this->insert(offset, buffer, stop - buffer);
522}
523
524void SkString::insertU64(size_t offset, uint64_t dec, int minDigits) {
525    char    buffer[SkStrAppendU64_MaxSize];
526    char*   stop = SkStrAppendU64(buffer, dec, minDigits);
527    this->insert(offset, buffer, stop - buffer);
528}
529
530void SkString::insertHex(size_t offset, uint32_t hex, int minDigits) {
531    minDigits = SkPin32(minDigits, 0, 8);
532
533    static const char gHex[] = "0123456789ABCDEF";
534
535    char    buffer[8];
536    char*   p = buffer + sizeof(buffer);
537
538    do {
539        *--p = gHex[hex & 0xF];
540        hex >>= 4;
541        minDigits -= 1;
542    } while (hex != 0);
543
544    while (--minDigits >= 0) {
545        *--p = '0';
546    }
547
548    SkASSERT(p >= buffer);
549    this->insert(offset, p, buffer + sizeof(buffer) - p);
550}
551
552void SkString::insertScalar(size_t offset, SkScalar value) {
553    char    buffer[SkStrAppendScalar_MaxSize];
554    char*   stop = SkStrAppendScalar(buffer, value);
555    this->insert(offset, buffer, stop - buffer);
556}
557
558void SkString::printf(const char format[], ...) {
559    char    buffer[kBufferSize];
560    ARGS_TO_BUFFER(format, buffer, kBufferSize);
561
562    this->set(buffer, strlen(buffer));
563}
564
565void SkString::appendf(const char format[], ...) {
566    char    buffer[kBufferSize];
567    ARGS_TO_BUFFER(format, buffer, kBufferSize);
568
569    this->append(buffer, strlen(buffer));
570}
571
572void SkString::appendVAList(const char format[], va_list args) {
573    char    buffer[kBufferSize];
574    VSNPRINTF(buffer, kBufferSize, format, args);
575
576    this->append(buffer, strlen(buffer));
577}
578
579void SkString::prependf(const char format[], ...) {
580    char    buffer[kBufferSize];
581    ARGS_TO_BUFFER(format, buffer, kBufferSize);
582
583    this->prepend(buffer, strlen(buffer));
584}
585
586///////////////////////////////////////////////////////////////////////////////
587
588void SkString::remove(size_t offset, size_t length) {
589    size_t size = this->size();
590
591    if (offset < size) {
592        if (offset + length > size) {
593            length = size - offset;
594        }
595        if (length > 0) {
596            SkASSERT(size > length);
597            SkString    tmp(size - length);
598            char*       dst = tmp.writable_str();
599            const char* src = this->c_str();
600
601            if (offset) {
602                SkASSERT(offset <= tmp.size());
603                memcpy(dst, src, offset);
604            }
605            size_t tail = size - offset - length;
606            SkASSERT((int32_t)tail >= 0);
607            if (tail) {
608        //      SkASSERT(offset + length <= tmp.size());
609                memcpy(dst + offset, src + offset + length, tail);
610            }
611            SkASSERT(dst[tmp.size()] == 0);
612            this->swap(tmp);
613        }
614    }
615}
616
617void SkString::swap(SkString& other) {
618    this->validate();
619    other.validate();
620
621    SkTSwap<Rec*>(fRec, other.fRec);
622#ifdef SK_DEBUG
623    SkTSwap<const char*>(fStr, other.fStr);
624#endif
625}
626
627///////////////////////////////////////////////////////////////////////////////
628
629SkString SkStringPrintf(const char* format, ...) {
630    SkString formattedOutput;
631    char buffer[kBufferSize];
632    ARGS_TO_BUFFER(format, buffer, kBufferSize);
633    formattedOutput.set(buffer);
634    return formattedOutput;
635}
636
637void SkStrSplit(const char* str, const char* delimiters, SkTArray<SkString>* out) {
638    const char* end = str + strlen(str);
639    while (str != end) {
640        // Find a token.
641        const size_t len = strcspn(str, delimiters);
642        out->push_back().set(str, len);
643        str += len;
644        // Skip any delimiters.
645        str += strspn(str, delimiters);
646    }
647}
648
649#undef VSNPRINTF
650#undef SNPRINTF
651