1/*
2 * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26
27/*
28 *  DESCRIPTION
29 *    Calculates cliping boundary for Affine functions.
30 *
31 */
32
33#include "mlib_image.h"
34#include "mlib_SysMath.h"
35#include "mlib_ImageAffine.h"
36#include "safe_math.h"
37
38
39/***************************************************************/
40mlib_status mlib_AffineEdges(mlib_affine_param *param,
41                             const mlib_image  *dst,
42                             const mlib_image  *src,
43                             void              *buff_lcl,
44                             mlib_s32          buff_size,
45                             mlib_s32          kw,
46                             mlib_s32          kh,
47                             mlib_s32          kw1,
48                             mlib_s32          kh1,
49                             mlib_edge         edge,
50                             const mlib_d64    *mtx,
51                             mlib_s32          shiftx,
52                             mlib_s32          shifty)
53{
54  mlib_u8 *buff = buff_lcl;
55  mlib_u8 **lineAddr = param->lineAddr;
56  mlib_s32 srcWidth, dstWidth, srcHeight, dstHeight, srcYStride, dstYStride;
57  mlib_s32 *leftEdges, *rightEdges, *xStarts, *yStarts, bsize0, bsize1 = 0;
58  mlib_u8 *srcData, *dstData;
59  mlib_u8 *paddings;
60  void *warp_tbl = NULL;
61  mlib_s32 yStart = 0, yFinish = -1, dX, dY;
62
63  mlib_d64 xClip, yClip, wClip, hClip;
64  mlib_d64 delta = 0.;
65  mlib_d64 minX, minY, maxX, maxY;
66
67  mlib_d64 coords[4][2];
68  mlib_d64 a = mtx[0], b = mtx[1], tx = mtx[2], c = mtx[3], d = mtx[4], ty = mtx[5];
69  mlib_d64 a2, b2, tx2, c2, d2, ty2;
70  mlib_d64 dx, dy, div;
71  mlib_s32 sdx, sdy;
72  mlib_d64 dTop;
73  mlib_d64 val0;
74  mlib_s32 top, bot;
75  mlib_s32 topIdx, max_xsize = 0;
76  mlib_s32 i, j, t;
77
78  srcData = mlib_ImageGetData(src);
79  dstData = mlib_ImageGetData(dst);
80  srcWidth = mlib_ImageGetWidth(src);
81  srcHeight = mlib_ImageGetHeight(src);
82  dstWidth = mlib_ImageGetWidth(dst);
83  dstHeight = mlib_ImageGetHeight(dst);
84  srcYStride = mlib_ImageGetStride(src);
85  dstYStride = mlib_ImageGetStride(dst);
86  paddings = mlib_ImageGetPaddings(src);
87
88  /* All the transformation matrix parameters should be finite. if not, return failure */
89  if (!(IS_FINITE(a) && IS_FINITE(b) && IS_FINITE(c) && IS_FINITE(d) &&
90        IS_FINITE(tx) && IS_FINITE(ty))) {
91    return MLIB_FAILURE;
92  }
93
94  if (srcWidth >= (1 << 15) || srcHeight >= (1 << 15)) {
95    return MLIB_FAILURE;
96  }
97
98  div = a * d - b * c;
99
100  if (div == 0.0) {
101    return MLIB_FAILURE;
102  }
103
104  bsize0 = (dstHeight * sizeof(mlib_s32) + 7) & ~7;
105
106  if (lineAddr == NULL) {
107    bsize1 = ((srcHeight + 4 * kh) * sizeof(mlib_u8 *) + 7) & ~7;
108  }
109
110  param->buff_malloc = NULL;
111
112  if ((4 * bsize0 + bsize1) > buff_size) {
113    buff = param->buff_malloc = mlib_malloc(4 * bsize0 + bsize1);
114
115    if (buff == NULL)
116      return MLIB_FAILURE;
117  }
118
119  leftEdges = (mlib_s32 *) (buff);
120  rightEdges = (mlib_s32 *) (buff += bsize0);
121  xStarts = (mlib_s32 *) (buff += bsize0);
122  yStarts = (mlib_s32 *) (buff += bsize0);
123
124  if (lineAddr == NULL) {
125    mlib_u8 *srcLinePtr = srcData;
126    lineAddr = (mlib_u8 **) (buff += bsize0);
127    for (i = 0; i < 2 * kh; i++)
128      lineAddr[i] = srcLinePtr;
129    lineAddr += 2 * kh;
130    for (i = 0; i < srcHeight - 1; i++) {
131      lineAddr[i] = srcLinePtr;
132      srcLinePtr += srcYStride;
133    }
134
135    for (i = srcHeight - 1; i < srcHeight + 2 * kh; i++)
136      lineAddr[i] = srcLinePtr;
137  }
138
139  if ((mlib_s32) edge < 0) {                               /* process edges */
140    minX = 0;
141    minY = 0;
142    maxX = srcWidth;
143    maxY = srcHeight;
144  }
145  else {
146
147    if (kw > 1)
148      delta = -0.5;                                        /* for MLIB_NEAREST filter delta = 0. */
149
150    minX = (kw1 - delta);
151    minY = (kh1 - delta);
152    maxX = srcWidth - ((kw - 1) - (kw1 - delta));
153    maxY = srcHeight - ((kh - 1) - (kh1 - delta));
154
155    if (edge == MLIB_EDGE_SRC_PADDED) {
156      if (minX < paddings[0])
157        minX = paddings[0];
158
159      if (minY < paddings[1])
160        minY = paddings[1];
161
162      if (maxX > (srcWidth - paddings[2]))
163        maxX = srcWidth - paddings[2];
164
165      if (maxY > (srcHeight - paddings[3]))
166        maxY = srcHeight - paddings[3];
167    }
168  }
169
170  xClip = minX;
171  yClip = minY;
172  wClip = maxX;
173  hClip = maxY;
174
175/*
176 *   STORE_PARAM(param, src);
177 *   STORE_PARAM(param, dst);
178 */
179  param->src = (void *)src;
180  param->dst = (void *)dst;
181  STORE_PARAM(param, lineAddr);
182  STORE_PARAM(param, dstData);
183  STORE_PARAM(param, srcYStride);
184  STORE_PARAM(param, dstYStride);
185  STORE_PARAM(param, leftEdges);
186  STORE_PARAM(param, rightEdges);
187  STORE_PARAM(param, xStarts);
188  STORE_PARAM(param, yStarts);
189  STORE_PARAM(param, max_xsize);
190  STORE_PARAM(param, yStart);
191  STORE_PARAM(param, yFinish);
192  STORE_PARAM(param, warp_tbl);
193
194  if ((xClip >= wClip) || (yClip >= hClip)) {
195    return MLIB_SUCCESS;
196  }
197
198  a2 = d;
199  b2 = -b;
200  tx2 = (-d * tx + b * ty);
201  c2 = -c;
202  d2 = a;
203  ty2 = (c * tx - a * ty);
204
205  dx = a2;
206  dy = c2;
207
208  tx -= 0.5;
209  ty -= 0.5;
210
211  coords[0][0] = xClip * a + yClip * b + tx;
212  coords[0][1] = xClip * c + yClip * d + ty;
213
214  coords[2][0] = wClip * a + hClip * b + tx;
215  coords[2][1] = wClip * c + hClip * d + ty;
216
217  if (div > 0) {
218    coords[1][0] = wClip * a + yClip * b + tx;
219    coords[1][1] = wClip * c + yClip * d + ty;
220
221    coords[3][0] = xClip * a + hClip * b + tx;
222    coords[3][1] = xClip * c + hClip * d + ty;
223  }
224  else {
225    coords[3][0] = wClip * a + yClip * b + tx;
226    coords[3][1] = wClip * c + yClip * d + ty;
227
228    coords[1][0] = xClip * a + hClip * b + tx;
229    coords[1][1] = xClip * c + hClip * d + ty;
230  }
231
232  topIdx = 0;
233  for (i = 1; i < 4; i++) {
234
235    if (coords[i][1] < coords[topIdx][1])
236      topIdx = i;
237  }
238
239  dTop = coords[topIdx][1];
240  val0 = dTop;
241  SAT32(top);
242  bot = -1;
243
244  if (top >= dstHeight) {
245    return MLIB_SUCCESS;
246  }
247
248  if (dTop >= 0.0) {
249    mlib_d64 xLeft, xRight, x;
250    mlib_s32 nextIdx;
251
252    if (dTop == top) {
253      xLeft = coords[topIdx][0];
254      xRight = coords[topIdx][0];
255      nextIdx = (topIdx + 1) & 0x3;
256
257      if (dTop == coords[nextIdx][1]) {
258        x = coords[nextIdx][0];
259        xLeft = (xLeft <= x) ? xLeft : x;
260        xRight = (xRight >= x) ? xRight : x;
261      }
262
263      nextIdx = (topIdx - 1) & 0x3;
264
265      if (dTop == coords[nextIdx][1]) {
266        x = coords[nextIdx][0];
267        xLeft = (xLeft <= x) ? xLeft : x;
268        xRight = (xRight >= x) ? xRight : x;
269      }
270
271      val0 = xLeft;
272      SAT32(t);
273      leftEdges[top] = (t >= xLeft) ? t : ++t;
274
275      if (xLeft >= MLIB_S32_MAX)
276        leftEdges[top] = MLIB_S32_MAX;
277
278      val0 = xRight;
279      SAT32(rightEdges[top]);
280    }
281    else
282      top++;
283  }
284  else
285    top = 0;
286
287  for (i = 0; i < 2; i++) {
288    mlib_d64 dY1 = coords[(topIdx - i) & 0x3][1];
289    mlib_d64 dX1 = coords[(topIdx - i) & 0x3][0];
290    mlib_d64 dY2 = coords[(topIdx - i - 1) & 0x3][1];
291    mlib_d64 dX2 = coords[(topIdx - i - 1) & 0x3][0];
292    mlib_d64 x = dX1, slope = (dX2 - dX1) / (dY2 - dY1);
293    mlib_s32 y1;
294    mlib_s32 y2;
295
296    if (dY1 == dY2)
297      continue;
298
299    if (!(IS_FINITE(slope))) {
300      continue;
301    }
302
303    if (dY1 < 0.0)
304      y1 = 0;
305    else {
306      val0 = dY1 + 1;
307      SAT32(y1);
308    }
309
310    val0 = dY2;
311    SAT32(y2);
312
313    if (y2 >= dstHeight)
314      y2 = (mlib_s32) (dstHeight - 1);
315
316    x += slope * (y1 - dY1);
317#ifdef __SUNPRO_C
318#pragma pipeloop(0)
319#endif /* __SUNPRO_C */
320    for (j = y1; j <= y2; j++) {
321      val0 = x;
322      SAT32(t);
323      leftEdges[j] = (t >= x) ? t : ++t;
324
325      if (x >= MLIB_S32_MAX)
326        leftEdges[j] = MLIB_S32_MAX;
327      x += slope;
328    }
329  }
330
331  for (i = 0; i < 2; i++) {
332    mlib_d64 dY1 = coords[(topIdx + i) & 0x3][1];
333    mlib_d64 dX1 = coords[(topIdx + i) & 0x3][0];
334    mlib_d64 dY2 = coords[(topIdx + i + 1) & 0x3][1];
335    mlib_d64 dX2 = coords[(topIdx + i + 1) & 0x3][0];
336    mlib_d64 x = dX1, slope = (dX2 - dX1) / (dY2 - dY1);
337    mlib_s32 y1;
338    mlib_s32 y2;
339
340    if (dY1 == dY2)
341      continue;
342
343    if (!(IS_FINITE(slope))) {
344      continue;
345    }
346
347    if (dY1 < 0.0)
348      y1 = 0;
349    else {
350      val0 = dY1 + 1;
351      SAT32(y1);
352    }
353
354    val0 = dY2;
355    SAT32(y2);
356
357    if (y2 >= dstHeight)
358      y2 = (mlib_s32) (dstHeight - 1);
359
360    x += slope * (y1 - dY1);
361#ifdef __SUNPRO_C
362#pragma pipeloop(0)
363#endif /* __SUNPRO_C */
364    for (j = y1; j <= y2; j++) {
365      val0 = x;
366      SAT32(rightEdges[j]);
367      x += slope;
368    }
369
370    bot = y2;
371  }
372
373  {
374    mlib_d64 dxCl = xClip * div;
375    mlib_d64 dyCl = yClip * div;
376    mlib_d64 dwCl = wClip * div;
377    mlib_d64 dhCl = hClip * div;
378
379    mlib_s32 xCl = (mlib_s32) (xClip + delta);
380    mlib_s32 yCl = (mlib_s32) (yClip + delta);
381    mlib_s32 wCl = (mlib_s32) (wClip + delta);
382    mlib_s32 hCl = (mlib_s32) (hClip + delta);
383
384    /*
385     * mlib_s32 xCl = (mlib_s32)(xClip + delta);
386     * mlib_s32 yCl = (mlib_s32)(yClip + delta);
387     * mlib_s32 wCl = (mlib_s32)(wClip);
388     * mlib_s32 hCl = (mlib_s32)(hClip);
389     */
390
391    if (edge == MLIB_EDGE_SRC_PADDED) {
392      xCl = kw1;
393      yCl = kh1;
394      wCl = (mlib_s32) (srcWidth - ((kw - 1) - kw1));
395      hCl = (mlib_s32) (srcHeight - ((kh - 1) - kh1));
396    }
397
398    div = 1.0 / div;
399
400    sdx = (mlib_s32) (a2 * div * (1 << shiftx));
401    sdy = (mlib_s32) (c2 * div * (1 << shifty));
402
403    if (div > 0) {
404
405#ifdef __SUNPRO_C
406#pragma pipeloop(0)
407#endif /* __SUNPRO_C */
408      for (i = top; i <= bot; i++) {
409        mlib_s32 xLeft = leftEdges[i];
410        mlib_s32 xRight = rightEdges[i];
411        mlib_s32 xs, ys, x_e, y_e, x_s, y_s;
412        mlib_d64 dxs, dys, dxe, dye;
413        mlib_d64 xl, ii, xr;
414
415        xLeft = (xLeft < 0) ? 0 : xLeft;
416        xRight = (xRight >= dstWidth) ? (mlib_s32) (dstWidth - 1) : xRight;
417
418        xl = xLeft + 0.5;
419        ii = i + 0.5;
420        xr = xRight + 0.5;
421        dxs = xl * a2 + ii * b2 + tx2;
422        dys = xl * c2 + ii * d2 + ty2;
423
424        if ((dxs < dxCl) || (dxs >= dwCl) || (dys < dyCl) || (dys >= dhCl)) {
425          dxs += dx;
426          dys += dy;
427          xLeft++;
428
429          if ((dxs < dxCl) || (dxs >= dwCl) || (dys < dyCl) || (dys >= dhCl))
430            xRight = -1;
431        }
432
433        dxe = xr * a2 + ii * b2 + tx2;
434        dye = xr * c2 + ii * d2 + ty2;
435
436        if ((dxe < dxCl) || (dxe >= dwCl) || (dye < dyCl) || (dye >= dhCl)) {
437          dxe -= dx;
438          dye -= dy;
439          xRight--;
440
441          if ((dxe < dxCl) || (dxe >= dwCl) || (dye < dyCl) || (dye >= dhCl))
442            xRight = -1;
443        }
444
445        xs = (mlib_s32) ((dxs * div + delta) * (1 << shiftx));
446        x_s = xs >> shiftx;
447
448        ys = (mlib_s32) ((dys * div + delta) * (1 << shifty));
449        y_s = ys >> shifty;
450
451        if (x_s < xCl)
452          xs = (xCl << shiftx);
453        else if (x_s >= wCl)
454          xs = ((wCl << shiftx) - 1);
455
456        if (y_s < yCl)
457          ys = (yCl << shifty);
458        else if (y_s >= hCl)
459          ys = ((hCl << shifty) - 1);
460
461        if (xRight >= xLeft) {
462          x_e = ((xRight - xLeft) * sdx + xs) >> shiftx;
463          y_e = ((xRight - xLeft) * sdy + ys) >> shifty;
464
465          if ((x_e < xCl) || (x_e >= wCl)) {
466            if (sdx > 0)
467              sdx -= 1;
468            else
469              sdx += 1;
470          }
471
472          if ((y_e < yCl) || (y_e >= hCl)) {
473            if (sdy > 0)
474              sdy -= 1;
475            else
476              sdy += 1;
477          }
478        }
479
480        leftEdges[i] = xLeft;
481        rightEdges[i] = xRight;
482        xStarts[i] = xs;
483        yStarts[i] = ys;
484
485        if ((xRight - xLeft + 1) > max_xsize)
486          max_xsize = (xRight - xLeft + 1);
487      }
488    }
489    else {
490
491#ifdef __SUNPRO_C
492#pragma pipeloop(0)
493#endif /* __SUNPRO_C */
494      for (i = top; i <= bot; i++) {
495        mlib_s32 xLeft = leftEdges[i];
496        mlib_s32 xRight = rightEdges[i];
497        mlib_s32 xs, ys, x_e, y_e, x_s, y_s;
498        mlib_d64 dxs, dys, dxe, dye;
499        mlib_d64 xl, ii, xr;
500
501        xLeft = (xLeft < 0) ? 0 : xLeft;
502        xRight = (xRight >= dstWidth) ? (mlib_s32) (dstWidth - 1) : xRight;
503
504        xl = xLeft + 0.5;
505        ii = i + 0.5;
506        xr = xRight + 0.5;
507        dxs = xl * a2 + ii * b2 + tx2;
508        dys = xl * c2 + ii * d2 + ty2;
509
510        if ((dxs > dxCl) || (dxs <= dwCl) || (dys > dyCl) || (dys <= dhCl)) {
511          dxs += dx;
512          dys += dy;
513          xLeft++;
514
515          if ((dxs > dxCl) || (dxs <= dwCl) || (dys > dyCl) || (dys <= dhCl))
516            xRight = -1;
517        }
518
519        dxe = xr * a2 + ii * b2 + tx2;
520        dye = xr * c2 + ii * d2 + ty2;
521
522        if ((dxe > dxCl) || (dxe <= dwCl) || (dye > dyCl) || (dye <= dhCl)) {
523          dxe -= dx;
524          dye -= dy;
525          xRight--;
526
527          if ((dxe > dxCl) || (dxe <= dwCl) || (dye > dyCl) || (dye <= dhCl))
528            xRight = -1;
529        }
530
531        xs = (mlib_s32) ((dxs * div + delta) * (1 << shiftx));
532        x_s = xs >> shiftx;
533
534        if (x_s < xCl)
535          xs = (xCl << shiftx);
536        else if (x_s >= wCl)
537          xs = ((wCl << shiftx) - 1);
538
539        ys = (mlib_s32) ((dys * div + delta) * (1 << shifty));
540        y_s = ys >> shifty;
541
542        if (y_s < yCl)
543          ys = (yCl << shifty);
544        else if (y_s >= hCl)
545          ys = ((hCl << shifty) - 1);
546
547        if (xRight >= xLeft) {
548          x_e = ((xRight - xLeft) * sdx + xs) >> shiftx;
549          y_e = ((xRight - xLeft) * sdy + ys) >> shifty;
550
551          if ((x_e < xCl) || (x_e >= wCl)) {
552            if (sdx > 0)
553              sdx -= 1;
554            else
555              sdx += 1;
556          }
557
558          if ((y_e < yCl) || (y_e >= hCl)) {
559            if (sdy > 0)
560              sdy -= 1;
561            else
562              sdy += 1;
563          }
564        }
565
566        leftEdges[i] = xLeft;
567        rightEdges[i] = xRight;
568        xStarts[i] = xs;
569        yStarts[i] = ys;
570
571        if ((xRight - xLeft + 1) > max_xsize)
572          max_xsize = (xRight - xLeft + 1);
573      }
574    }
575  }
576
577  while (leftEdges[top] > rightEdges[top] && top <= bot)
578    top++;
579
580  if (top < bot)
581    while (leftEdges[bot] > rightEdges[bot])
582      bot--;
583
584  yStart = top;
585  yFinish = bot;
586  dX = sdx;
587  dY = sdy;
588
589  dstData += (yStart - 1) * dstYStride;
590
591  STORE_PARAM(param, dstData);
592  STORE_PARAM(param, yStart);
593  STORE_PARAM(param, yFinish);
594  STORE_PARAM(param, max_xsize);
595  STORE_PARAM(param, dX);
596  STORE_PARAM(param, dY);
597
598  return MLIB_SUCCESS;
599}
600
601/***************************************************************/
602