| File: | Poly.c |
| Location: | line 173, column 11 |
| Description: | Dereference of null pointer |
| 1 | /* | |||
| 2 | * | |||
| 3 | * Copyright © 2002 Keith Packard | |||
| 4 | * | |||
| 5 | * Permission to use, copy, modify, distribute, and sell this software and its | |||
| 6 | * documentation for any purpose is hereby granted without fee, provided that | |||
| 7 | * the above copyright notice appear in all copies and that both that | |||
| 8 | * copyright notice and this permission notice appear in supporting | |||
| 9 | * documentation, and that the name of Keith Packard not be used in | |||
| 10 | * advertising or publicity pertaining to distribution of the software without | |||
| 11 | * specific, written prior permission. Keith Packard makes no | |||
| 12 | * representations about the suitability of this software for any purpose. It | |||
| 13 | * is provided "as is" without express or implied warranty. | |||
| 14 | * | |||
| 15 | * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, | |||
| 16 | * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO | |||
| 17 | * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR | |||
| 18 | * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, | |||
| 19 | * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER | |||
| 20 | * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR | |||
| 21 | * PERFORMANCE OF THIS SOFTWARE. | |||
| 22 | */ | |||
| 23 | ||||
| 24 | #ifdef HAVE_CONFIG_H1 | |||
| 25 | #include <config.h> | |||
| 26 | #endif | |||
| 27 | #include "Xrenderint.h" | |||
| 28 | ||||
| 29 | typedef struct _Edge Edge; | |||
| 30 | ||||
| 31 | struct _Edge { | |||
| 32 | XLineFixed edge; | |||
| 33 | XFixed current_x; | |||
| 34 | Boolint clockWise; | |||
| 35 | Edge *next, *prev; | |||
| 36 | }; | |||
| 37 | ||||
| 38 | static int | |||
| 39 | CompareEdge (const void *o1, const void *o2) | |||
| 40 | { | |||
| 41 | const Edge *e1 = o1, *e2 = o2; | |||
| 42 | ||||
| 43 | return e1->edge.p1.y - e2->edge.p1.y; | |||
| 44 | } | |||
| 45 | ||||
| 46 | static XFixed | |||
| 47 | XRenderComputeX (XLineFixed *line, XFixed y) | |||
| 48 | { | |||
| 49 | XFixed dx = line->p2.x - line->p1.x; | |||
| 50 | double ex = (double) (y - line->p1.y) * (double) dx; | |||
| 51 | XFixed dy = line->p2.y - line->p1.y; | |||
| 52 | ||||
| 53 | return (XFixed) line->p1.x + (XFixed) (ex / dy); | |||
| 54 | } | |||
| 55 | ||||
| 56 | static double | |||
| 57 | XRenderComputeInverseSlope (XLineFixed *l) | |||
| 58 | { | |||
| 59 | return (XFixedToDouble (l->p2.x - l->p1.x)(((XDouble) (l->p2.x - l->p1.x)) / 65536) / | |||
| 60 | XFixedToDouble (l->p2.y - l->p1.y)(((XDouble) (l->p2.y - l->p1.y)) / 65536)); | |||
| 61 | } | |||
| 62 | ||||
| 63 | static double | |||
| 64 | XRenderComputeXIntercept (XLineFixed *l, double inverse_slope) | |||
| 65 | { | |||
| 66 | return XFixedToDouble (l->p1.x)(((XDouble) (l->p1.x)) / 65536) - inverse_slope * XFixedToDouble (l->p1.y)(((XDouble) (l->p1.y)) / 65536); | |||
| 67 | } | |||
| 68 | ||||
| 69 | static XFixed | |||
| 70 | XRenderComputeIntersect (XLineFixed *l1, XLineFixed *l2) | |||
| 71 | { | |||
| 72 | /* | |||
| 73 | * x = m1y + b1 | |||
| 74 | * x = m2y + b2 | |||
| 75 | * m1y + b1 = m2y + b2 | |||
| 76 | * y * (m1 - m2) = b2 - b1 | |||
| 77 | * y = (b2 - b1) / (m1 - m2) | |||
| 78 | */ | |||
| 79 | double m1 = XRenderComputeInverseSlope (l1); | |||
| 80 | double b1 = XRenderComputeXIntercept (l1, m1); | |||
| 81 | double m2 = XRenderComputeInverseSlope (l2); | |||
| 82 | double b2 = XRenderComputeXIntercept (l2, m2); | |||
| 83 | ||||
| 84 | return XDoubleToFixed ((b2 - b1) / (m1 - m2))((XFixed) (((b2 - b1) / (m1 - m2)) * 65536)); | |||
| 85 | } | |||
| 86 | ||||
| 87 | static int | |||
| 88 | XRenderComputeTrapezoids (Edge *edges, | |||
| 89 | int nedges, | |||
| 90 | int winding, | |||
| 91 | XTrapezoid *traps) | |||
| 92 | { | |||
| 93 | int ntraps = 0; | |||
| 94 | int inactive; | |||
| 95 | Edge *active; | |||
| 96 | Edge *e, *en, *next; | |||
| 97 | XFixed y, next_y, intersect; | |||
| 98 | ||||
| 99 | qsort (edges, nedges, sizeof (Edge), CompareEdge); | |||
| 100 | ||||
| 101 | y = edges[0].edge.p1.y; | |||
| 102 | active = NULL((void*)0); | |||
| 103 | inactive = 0; | |||
| 104 | while (active || inactive < nedges) | |||
| ||||
| 105 | { | |||
| 106 | /* insert new active edges into list */ | |||
| 107 | while (inactive < nedges) | |||
| 108 | { | |||
| 109 | e = &edges[inactive]; | |||
| 110 | if (e->edge.p1.y > y) | |||
| 111 | break; | |||
| 112 | /* move this edge into the active list */ | |||
| 113 | inactive++; | |||
| 114 | e->next = active; | |||
| 115 | e->prev = NULL((void*)0); | |||
| 116 | if (active) | |||
| 117 | active->prev = e; | |||
| 118 | active = e; | |||
| 119 | } | |||
| 120 | /* compute x coordinates along this group */ | |||
| 121 | for (e = active; e; e = e->next) | |||
| 122 | e->current_x = XRenderComputeX (&e->edge, y); | |||
| 123 | ||||
| 124 | /* sort active list */ | |||
| 125 | for (e = active; e; e = next) | |||
| 126 | { | |||
| 127 | next = e->next; | |||
| 128 | /* | |||
| 129 | * Find one later in the list that belongs before the | |||
| 130 | * current one | |||
| 131 | */ | |||
| 132 | for (en = next; en; en = en->next) | |||
| 133 | { | |||
| 134 | if (en->current_x < e->current_x || | |||
| 135 | (en->current_x == e->current_x && | |||
| 136 | en->edge.p2.x < e->edge.p2.x)) | |||
| 137 | { | |||
| 138 | /* | |||
| 139 | * insert en before e | |||
| 140 | * | |||
| 141 | * extract en | |||
| 142 | */ | |||
| 143 | en->prev->next = en->next; | |||
| 144 | if (en->next) | |||
| 145 | en->next->prev = en->prev; | |||
| 146 | /* | |||
| 147 | * insert en | |||
| 148 | */ | |||
| 149 | if (e->prev) | |||
| 150 | e->prev->next = en; | |||
| 151 | else | |||
| 152 | active = en; | |||
| 153 | en->prev = e->prev; | |||
| 154 | e->prev = en; | |||
| 155 | en->next = e; | |||
| 156 | /* | |||
| 157 | * start over at en | |||
| 158 | */ | |||
| 159 | next = en; | |||
| 160 | break; | |||
| 161 | } | |||
| 162 | } | |||
| 163 | } | |||
| 164 | #if 0 | |||
| 165 | printf ("y: %6.3g:", y / 65536.0); | |||
| 166 | for (e = active; e; e = e->next) | |||
| 167 | { | |||
| 168 | printf (" %6.3g", e->current_x / 65536.0); | |||
| 169 | } | |||
| 170 | printf ("\n"); | |||
| 171 | #endif | |||
| 172 | /* find next inflection point */ | |||
| 173 | next_y = active->edge.p2.y; | |||
| ||||
| 174 | for (e = active; e; e = en) | |||
| 175 | { | |||
| 176 | if (e->edge.p2.y < next_y) | |||
| 177 | next_y = e->edge.p2.y; | |||
| 178 | en = e->next; | |||
| 179 | /* check intersect */ | |||
| 180 | if (en && e->edge.p2.x > en->edge.p2.x) | |||
| 181 | { | |||
| 182 | intersect = XRenderComputeIntersect (&e->edge, &e->next->edge); | |||
| 183 | /* make sure this point is below the actual intersection */ | |||
| 184 | intersect = intersect + 1; | |||
| 185 | if (intersect < next_y) | |||
| 186 | next_y = intersect; | |||
| 187 | } | |||
| 188 | } | |||
| 189 | /* check next inactive point */ | |||
| 190 | if (inactive < nedges && edges[inactive].edge.p1.y < next_y) | |||
| 191 | next_y = edges[inactive].edge.p1.y; | |||
| 192 | ||||
| 193 | /* walk the list generating trapezoids */ | |||
| 194 | for (e = active; e && (en = e->next); e = en->next) | |||
| 195 | { | |||
| 196 | traps->top = y; | |||
| 197 | traps->bottom = next_y; | |||
| 198 | traps->left = e->edge; | |||
| 199 | traps->right = en->edge; | |||
| 200 | traps++; | |||
| 201 | ntraps++; | |||
| 202 | } | |||
| 203 | ||||
| 204 | y = next_y; | |||
| 205 | ||||
| 206 | /* delete inactive edges from list */ | |||
| 207 | for (e = active; e; e = next) | |||
| 208 | { | |||
| 209 | next = e->next; | |||
| 210 | if (e->edge.p2.y <= y) | |||
| 211 | { | |||
| 212 | if (e->prev) | |||
| 213 | e->prev->next = e->next; | |||
| 214 | else | |||
| 215 | active = e->next; | |||
| 216 | if (e->next) | |||
| 217 | e->next->prev = e->prev; | |||
| 218 | } | |||
| 219 | } | |||
| 220 | } | |||
| 221 | return ntraps; | |||
| 222 | } | |||
| 223 | ||||
| 224 | void | |||
| 225 | XRenderCompositeDoublePoly (Display *dpy, | |||
| 226 | int op, | |||
| 227 | Picture src, | |||
| 228 | Picture dst, | |||
| 229 | _Xconstconst XRenderPictFormat *maskFormat, | |||
| 230 | int xSrc, | |||
| 231 | int ySrc, | |||
| 232 | int xDst, | |||
| 233 | int yDst, | |||
| 234 | _Xconstconst XPointDouble *fpoints, | |||
| 235 | int npoints, | |||
| 236 | int winding) | |||
| 237 | { | |||
| 238 | Edge *edges; | |||
| 239 | XTrapezoid *traps; | |||
| 240 | int i, nedges, ntraps; | |||
| 241 | XFixed x, y, prevx = 0, prevy = 0, firstx = 0, firsty = 0; | |||
| 242 | XFixed top = 0, bottom = 0; /* GCCism */ | |||
| 243 | ||||
| 244 | edges = (Edge *) Xmalloc (npoints * sizeof (Edge) +malloc(((npoints * sizeof (Edge) + (npoints * npoints * sizeof (XTrapezoid))) == 0 ? 1 : (npoints * sizeof (Edge) + (npoints * npoints * sizeof (XTrapezoid))))) | |||
| 245 | (npoints * npoints * sizeof (XTrapezoid)))malloc(((npoints * sizeof (Edge) + (npoints * npoints * sizeof (XTrapezoid))) == 0 ? 1 : (npoints * sizeof (Edge) + (npoints * npoints * sizeof (XTrapezoid))))); | |||
| 246 | if (!edges) | |||
| 247 | return; | |||
| 248 | traps = (XTrapezoid *) (edges + npoints); | |||
| 249 | nedges = 0; | |||
| 250 | for (i = 0; i <= npoints; i++) | |||
| 251 | { | |||
| 252 | if (i == npoints) | |||
| 253 | { | |||
| 254 | x = firstx; | |||
| 255 | y = firsty; | |||
| 256 | } | |||
| 257 | else | |||
| 258 | { | |||
| 259 | x = XDoubleToFixed (fpoints[i].x)((XFixed) ((fpoints[i].x) * 65536)); | |||
| 260 | y = XDoubleToFixed (fpoints[i].y)((XFixed) ((fpoints[i].y) * 65536)); | |||
| 261 | } | |||
| 262 | if (i) | |||
| 263 | { | |||
| 264 | if (y < top) | |||
| 265 | top = y; | |||
| 266 | else if (y > bottom) | |||
| 267 | bottom = y; | |||
| 268 | if (prevy < y) | |||
| 269 | { | |||
| 270 | edges[nedges].edge.p1.x = prevx; | |||
| 271 | edges[nedges].edge.p1.y = prevy; | |||
| 272 | edges[nedges].edge.p2.x = x; | |||
| 273 | edges[nedges].edge.p2.y = y; | |||
| 274 | edges[nedges].clockWise = True1; | |||
| 275 | nedges++; | |||
| 276 | } | |||
| 277 | else if (prevy > y) | |||
| 278 | { | |||
| 279 | edges[nedges].edge.p1.x = x; | |||
| 280 | edges[nedges].edge.p1.y = y; | |||
| 281 | edges[nedges].edge.p2.x = prevx; | |||
| 282 | edges[nedges].edge.p2.y = prevy; | |||
| 283 | edges[nedges].clockWise = False0; | |||
| 284 | nedges++; | |||
| 285 | } | |||
| 286 | /* drop horizontal edges */ | |||
| 287 | } | |||
| 288 | else | |||
| 289 | { | |||
| 290 | top = y; | |||
| 291 | bottom = y; | |||
| 292 | firstx = x; | |||
| 293 | firsty = y; | |||
| 294 | } | |||
| 295 | prevx = x; | |||
| 296 | prevy = y; | |||
| 297 | } | |||
| 298 | ntraps = XRenderComputeTrapezoids (edges, nedges, winding, traps); | |||
| 299 | /* XXX adjust xSrc/xDst */ | |||
| 300 | XRenderCompositeTrapezoids (dpy, op, src, dst, maskFormat, xSrc, ySrc, traps, ntraps); | |||
| 301 | Xfree (edges)free((edges)); | |||
| 302 | } |