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
9
10#include "SkClampRange.h"
11
12/*
13 *  returns [0..count] for the number of steps (<= count) for which x0 <= edge
14 *  given each step is followed by x0 += dx
15 */
16static int chop(int64_t x0, SkFixed edge, int64_t x1, int64_t dx, int count) {
17    SkASSERT(dx > 0);
18    SkASSERT(count >= 0);
19
20    if (x0 >= edge) {
21        return 0;
22    }
23    if (x1 <= edge) {
24        return count;
25    }
26    int64_t n = (edge - x0 + dx - 1) / dx;
27    SkASSERT(n >= 0);
28    SkASSERT(n <= count);
29    return (int)n;
30}
31
32static bool overflows_fixed(int64_t x) {
33    return x < -SK_FixedMax || x > SK_FixedMax;
34}
35
36void SkClampRange::initFor1(SkFixed fx) {
37    fCount0 = fCount1 = fCount2 = 0;
38    if (fx <= 0) {
39        fCount0 = 1;
40    } else if (fx < 0xFFFF) {
41        fCount1 = 1;
42        fFx1 = fx;
43    } else {
44        fCount2 = 1;
45    }
46}
47
48void SkClampRange::init(SkFixed fx0, SkFixed dx0, int count, int v0, int v1) {
49    SkASSERT(count > 0);
50
51    fV0 = v0;
52    fV1 = v1;
53    fOverflowed = false;
54
55    // special case 1 == count, as it is slightly common for skia
56    // and avoids us ever calling divide or 64bit multiply
57    if (1 == count) {
58        this->initFor1(fx0);
59        return;
60    }
61
62    int64_t fx = fx0;
63    int64_t dx = dx0;
64    // start with ex equal to the last computed value
65    int64_t ex = fx + (count - 1) * dx;
66    fOverflowed = overflows_fixed(ex);
67
68    if ((uint64_t)(fx | ex) <= 0xFFFF) {
69        fCount0 = fCount2 = 0;
70        fCount1 = count;
71        fFx1 = fx0;
72        return;
73    }
74    if (fx <= 0 && ex <= 0) {
75        fCount1 = fCount2 = 0;
76        fCount0 = count;
77        return;
78    }
79    if (fx >= 0xFFFF && ex >= 0xFFFF) {
80        fCount0 = fCount1 = 0;
81        fCount2 = count;
82        return;
83    }
84
85    int extraCount = 0;
86
87    // now make ex be 1 past the last computed value
88    ex += dx;
89    fOverflowed = overflows_fixed(ex);
90    // now check for over/under flow
91    if (fOverflowed) {
92        int originalCount = count;
93        int64_t ccount;
94        bool swap = dx < 0;
95        if (swap) {
96            dx = -dx;
97            fx = -fx;
98        }
99        ccount = (SK_FixedMax - fx + dx - 1) / dx;
100        if (swap) {
101            dx = -dx;
102            fx = -fx;
103        }
104        SkASSERT(ccount > 0 && ccount <= SK_FixedMax);
105
106        count = (int)ccount;
107        if (0 == count) {
108            this->initFor1(fx0);
109            if (dx > 0) {
110                fCount2 += originalCount - 1;
111            } else {
112                fCount0 += originalCount - 1;
113            }
114            return;
115        }
116        extraCount = originalCount - count;
117        ex = fx + dx * count;
118    }
119
120    bool doSwap = dx < 0;
121
122    if (doSwap) {
123        ex -= dx;
124        fx -= dx;
125        SkTSwap(fx, ex);
126        dx = -dx;
127    }
128
129
130    fCount0 = chop(fx, 0, ex, dx, count);
131    count -= fCount0;
132    fx += fCount0 * dx;
133    SkASSERT(fx >= 0);
134    SkASSERT(fCount0 == 0 || (fx - dx) < 0);
135    fCount1 = chop(fx, 0xFFFF, ex, dx, count);
136    count -= fCount1;
137    fCount2 = count;
138
139#ifdef SK_DEBUG
140    fx += fCount1 * dx;
141    SkASSERT(fx <= ex);
142    if (fCount2 > 0) {
143        SkASSERT(fx >= 0xFFFF);
144        if (fCount1 > 0) {
145            SkASSERT(fx - dx < 0xFFFF);
146        }
147    }
148#endif
149
150    if (doSwap) {
151        SkTSwap(fCount0, fCount2);
152        SkTSwap(fV0, fV1);
153        dx = -dx;
154    }
155
156    if (fCount1 > 0) {
157        fFx1 = fx0 + fCount0 * (int)dx;
158    }
159
160    if (dx > 0) {
161        fCount2 += extraCount;
162    } else {
163        fCount0 += extraCount;
164    }
165}
166