diff options
| author | Jabier Arraiza Cenoz <jabier.arraiza@marker.es> | 2015-03-31 10:57:18 +0000 |
|---|---|---|
| committer | Jabiertxof <jtx@jtx.marker.es> | 2015-03-31 10:57:18 +0000 |
| commit | 04019f73cb42d7b23bfe8c51137d5e84f25223cf (patch) | |
| tree | ca0db6e97de907ffcf2ea1f6b7565ff38c6795c4 /src | |
| parent | end append path (diff) | |
| parent | Updating Potrace from 1.10 to 1.12, fixing Bug #1438366 (CVE-2013-7437 vulner... (diff) | |
| download | inkscape-04019f73cb42d7b23bfe8c51137d5e84f25223cf.tar.gz inkscape-04019f73cb42d7b23bfe8c51137d5e84f25223cf.zip | |
update to trunk
(bzr r13645.1.58)
Diffstat (limited to 'src')
| -rw-r--r-- | src/2geom/line.h | 17 | ||||
| -rw-r--r-- | src/helper/geom-pathstroke.cpp | 185 | ||||
| -rw-r--r-- | src/trace/potrace/auxiliary.h | 31 | ||||
| -rw-r--r-- | src/trace/potrace/bitmap.h | 33 | ||||
| -rw-r--r-- | src/trace/potrace/bitops.h | 83 | ||||
| -rw-r--r-- | src/trace/potrace/curve.cpp | 26 | ||||
| -rw-r--r-- | src/trace/potrace/curve.h | 2 | ||||
| -rw-r--r-- | src/trace/potrace/decompose.cpp | 29 | ||||
| -rw-r--r-- | src/trace/potrace/decompose.h | 2 | ||||
| -rw-r--r-- | src/trace/potrace/greymap.cpp | 61 | ||||
| -rw-r--r-- | src/trace/potrace/greymap.h | 5 | ||||
| -rw-r--r-- | src/trace/potrace/lists.h | 2 | ||||
| -rw-r--r-- | src/trace/potrace/potracelib.cpp | 2 | ||||
| -rw-r--r-- | src/trace/potrace/potracelib.h | 2 | ||||
| -rw-r--r-- | src/trace/potrace/progress.h | 2 | ||||
| -rw-r--r-- | src/trace/potrace/render.cpp | 4 | ||||
| -rw-r--r-- | src/trace/potrace/render.h | 2 | ||||
| -rw-r--r-- | src/trace/potrace/trace.cpp | 66 | ||||
| -rw-r--r-- | src/trace/potrace/trace.h | 2 |
19 files changed, 407 insertions, 149 deletions
diff --git a/src/2geom/line.h b/src/2geom/line.h index ade67f818..cbd68fa08 100644 --- a/src/2geom/line.h +++ b/src/2geom/line.h @@ -35,6 +35,7 @@ #define LIB2GEOM_SEEN_LINE_H #include <cmath> +#include <iostream> #include <boost/optional.hpp> #include <2geom/bezier-curve.h> // for LineSegment #include <2geom/rect.h> @@ -258,9 +259,19 @@ public: dist = -dot(n, m_origin); return n; } - /// @} + + friend inline std::ostream &operator<< (std::ostream &out_file, const Geom::Line &in_line); +/// @} }; // end class Line +/** @brief Output operator for lines. + * Prints out representation (point + versor) + */ +inline std::ostream &operator<< (std::ostream &out_file, const Geom::Line &in_line) { + out_file << "X: " << in_line.m_origin[X] << " Y: " << in_line.m_origin[Y] + << " dX: " << in_line.m_versor[X] << " dY: " << in_line.m_versor[Y]; + return out_file; +} inline double distance(Point const& _point, Line const& _line) @@ -365,6 +376,10 @@ inline Line make_angle_bisector_line(Point const& A, Point const& O, Point const& B) { Point M = middle_point(A,B); + if (are_near(O,M)) { + Line l(A,B); + M += (make_orthogonal_line(O,l)).versor(); + } return Line(O,M); } diff --git a/src/helper/geom-pathstroke.cpp b/src/helper/geom-pathstroke.cpp index 1908f2db7..aaafea98f 100644 --- a/src/helper/geom-pathstroke.cpp +++ b/src/helper/geom-pathstroke.cpp @@ -159,6 +159,7 @@ void miter_join_internal(Geom::Path& res, Geom::Curve const& outgoing, double mi Geom::Point p = Geom::intersection_point(incoming.finalPoint(), tang1, outgoing.initialPoint(), tang2); bool satisfied = false; + bool inc_ls = res.back_open().degreesOfFreedom() <= 4; if (p.isFinite()) { // check size of miter @@ -166,32 +167,20 @@ void miter_join_internal(Geom::Path& res, Geom::Curve const& outgoing, double mi satisfied = Geom::distance(p, point_on_path) <= miter * 2.0 * width; if (satisfied) { // miter OK, check to see if we can do a relocation - bool ls = res.back_open().degreesOfFreedom() <= 4; - if (ls) { + if (inc_ls) { res.setFinal(p); } else { res.appendNew<Geom::LineSegment>(p); } } else if (clip) { // miter needs clipping, find two points - Geom::Line bisector(point_on_path, p); - Geom::Point point_limit = point_on_path + miter * 2.0 * width * bisector.versor(); + Geom::Point bisector_versor = Geom::Line(point_on_path, p).versor(); + Geom::Point point_limit = point_on_path + miter * 2.0 * width * bisector_versor; - Geom::Line line_limit = - Geom::Line::from_origin_and_versor( point_limit, bisector.versor().cw() ); + Geom::Point p1 = Geom::intersection_point(incoming.finalPoint(), tang1, point_limit, bisector_versor.cw()); + Geom::Point p2 = Geom::intersection_point(outgoing.initialPoint(), tang2, point_limit, bisector_versor.cw()); - Geom::Line incoming_line( incoming.finalPoint(), p ); - Geom::Line outgoing_line( p, outgoing.initialPoint() ); - - Geom::OptCrossing i1 = intersection( line_limit, incoming_line ); - Geom::OptCrossing i2 = intersection( line_limit, outgoing_line ); - - // It would be nice to have a simple point returned by intersection! - Geom::Point p1 = line_limit.pointAt( (*i1).ta ); - Geom::Point p2 = line_limit.pointAt( (*i2).ta ); - - bool ls = res.back_open().degreesOfFreedom() <= 4; - if (ls) { + if (inc_ls) { res.setFinal(p1); } else { res.appendNew<Geom::LineSegment>(p1); @@ -203,9 +192,9 @@ void miter_join_internal(Geom::Path& res, Geom::Curve const& outgoing, double mi res.appendNew<Geom::LineSegment>(outgoing.initialPoint()); // check if we can do another relocation - bool ls = outgoing.degreesOfFreedom() <= 4; + bool out_ls = outgoing.degreesOfFreedom() <= 4; - if ( (satisfied || clip) && ls) { + if ( (satisfied || clip) && out_ls) { res.setFinal(outgoing.finalPoint()); } else { res.append(outgoing); @@ -236,12 +225,14 @@ Geom::Point pick_solution(Geom::Point points[2], Geom::Point tang2, Geom::Point return sol; } -void extrapolate_join(Geom::Path& path_builder, Geom::Curve const& outgoing, double miter_limit, double line_width) +void extrapolate_join(Geom::Path& path_builder, Geom::Curve const& outgoing, double miter, double width) { using namespace Geom; Geom::Curve const& incoming = path_builder.back(); + Geom::Point startPt = incoming.finalPoint(); Geom::Point endPt = outgoing.initialPoint(); - Geom::Point tang2 = Geom::unitTangentAt(outgoing.toSBasis(), 0); + Geom::Point tang1 = Geom::unitTangentAt(reverse(incoming.toSBasis()), 0.); + Geom::Point tang2 = outgoing.unitTangentAt(0); Geom::Circle circle1 = Geom::touching_circle(Geom::reverse(incoming.toSBasis()), 0.); Geom::Circle circle2 = Geom::touching_circle(outgoing.toSBasis(), 0); @@ -252,52 +243,160 @@ void extrapolate_join(Geom::Path& path_builder, Geom::Curve const& outgoing, dou Geom::Point points[2]; int solutions = 0; - Geom::EllipticalArc *arc0 = NULL; Geom::EllipticalArc *arc1 = NULL; + Geom::EllipticalArc *arc2 = NULL; + Geom::Point sol; + Geom::Point p1; + Geom::Point p2; if (!inc_ls && !out_ls) { + // Two circles solutions = Geom::circle_circle_intersection(circle1.center(), circle1.ray(), circle2.center(), circle2.ray(), points[0], points[1]); if (solutions == 2) { - Geom::Point sol = pick_solution(points, tang2, endPt); - - arc0 = circle1.arc(incoming.finalPoint(), 0.5*(incoming.finalPoint()+sol), sol, true); - arc1 = circle2.arc(sol, 0.5*(sol+endPt), endPt, true); + sol = pick_solution(points, tang2, endPt); + arc1 = circle1.arc(startPt, 0.5*(startPt+sol), sol, true); + arc2 = circle2.arc(sol, 0.5*(sol+endPt), endPt, true); } } else if (inc_ls && !out_ls) { + // Line and circle solutions = Geom::circle_line_intersection(circle2, incoming.initialPoint(), incoming.finalPoint(), points[0], points[1]); if (solutions == 2) { - Geom::Point sol = pick_solution(points, tang2, endPt); - path_builder.setFinal(sol); - arc1 = circle2.arc(sol, 0.5*(sol+endPt), endPt, true); + sol = pick_solution(points, tang2, endPt); + arc2 = circle2.arc(sol, 0.5*(sol+endPt), endPt, true); } } else if (!inc_ls && out_ls) { + // Circle and line solutions = Geom::circle_line_intersection(circle1, outgoing.initialPoint(), outgoing.finalPoint(), points[0], points[1]); if (solutions == 2) { - Geom::Point sol = pick_solution(points, tang2, endPt); - arc0 = circle1.arc(incoming.finalPoint(), 0.5*(sol+incoming.finalPoint()), sol, true); + sol = pick_solution(points, tang2, endPt); + arc1 = circle1.arc(startPt, 0.5*(sol+startPt), sol, true); } } if (solutions != 2) // no solutions available, fall back to miter - return miter_join(path_builder, outgoing, miter_limit, line_width); + return miter_clip_join(path_builder, outgoing, miter, width); + + // We have a solution, thus sol is defined. + p1 = sol; + + // See if we need to clip. Miter length is measured along a circular arc that is tangent to the + // bisector of the incoming and out going angles and passes through the end point (sol) of the + // line join. + + // Center of circle is intersection of a line orthogonal to bisector and a line bisecting + // a chord connecting the path end point (point_on_path) and the join end point (sol). + Geom::Point point_on_path = startPt + Geom::rot90(tang1)*width; + Geom::Line bisector = make_angle_bisector_line( startPt, point_on_path, endPt ); + Geom::Line ortho = make_orthogonal_line(point_on_path, bisector); + + Geom::LineSegment chord( point_on_path, sol ); + Geom::Line bisector_chord = make_bisector_line( chord ); + + Geom::Line limit_line; + double miter_limit = 2.0 * width * miter; + bool clipped = false; + + if( are_parallel( bisector_chord, ortho ) ) { + + // No intersection (can happen if curvatures are equal but opposite) + if( Geom::distance( point_on_path, sol ) > miter_limit ) { + clipped = true; + Geom::Point limit_point = point_on_path + miter_limit * bisector.versor(); + limit_line = make_parallel_line( limit_point, ortho ); + } + + } else { + + Geom::Point center = + Geom::intersection_point( bisector_chord.pointAt(0), bisector_chord.versor(), + ortho.pointAt(0), ortho.versor() ); + Geom::Coord radius = distance( center, point_on_path ); + Geom::Circle circle_center( center, radius ); + + double limit_angle = miter_limit / radius; + Geom::Ray start_ray( center, point_on_path ); + Geom::Ray end_ray( center, sol ); + Geom::Line limit_line( center, 0 ); // Angle set below + + if( Geom::cross( start_ray.versor(), end_ray.versor() ) > 0 ) { + limit_line.setAngle( start_ray.angle() - limit_angle ); + } else { + limit_line.setAngle( start_ray.angle() + limit_angle ); + } + + Geom::EllipticalArc* arc_center = circle_center.arc(point_on_path, 0.5*(point_on_path + sol), sol, true); + if( arc_center && arc_center->sweepAngle() > limit_angle ) { + // We need to clip + clipped = true; - if (arc0) - path_builder.append(*arc0); - if (arc1) + if (!inc_ls ) { + // Incoming circular + solutions = Geom::circle_line_intersection(circle1, limit_line.pointAt(0), limit_line.pointAt(1), points[0], points[1]); + + if (solutions == 2) { + p1 = pick_solution(points, tang2, endPt); + delete arc1; + arc1 = circle1.arc(startPt, 0.5*(p1+startPt), p1, true); + } + } else { + p1 = Geom::intersection_point( startPt, tang1, limit_line.pointAt(0), limit_line.versor() ); + } + + if (!out_ls ) { + // Outgoing circular + solutions = Geom::circle_line_intersection(circle2, limit_line.pointAt(0), limit_line.pointAt(1), points[0], points[1]); + + if (solutions == 2) { + p2 = pick_solution(points, tang1, endPt); + delete arc2; + arc2 = circle2.arc(p2, 0.5*(p2+endPt), endPt, true); + } + } else { + p2 = Geom::intersection_point( endPt, tang2, limit_line.pointAt(0), limit_line.versor() ); + } + } + // std::cout << " IFP: " << startPt + // << " POP: " << point_on_path + // << " OIP: " << endPt << std::endl; + // std::cout << " center: " << center << std::endl; + // std::cout << " radius: " << radius << std::endl; + // std::cout << " miter_limit: " << miter_limit << std::endl; + // std::cout << " limit_angle: " << limit_angle << std::endl; + // std::cout << " start_ray: " << Geom::Line( start_ray ) << std::endl; + // std::cout << " limit_line: " << limit_line << std::endl; + // std::cout << " P1 out: " << p1 << std::endl; + // std::cout << " P2 out: " << p2 << std::endl; + } + + // Add initial + if (arc1) { path_builder.append(*arc1); + } else { + // Straight line segment: move last point + path_builder.setFinal(p1); + } - delete arc0; - delete arc1; + if( clipped ) { + path_builder.appendNew<Geom::LineSegment>(p2); + } - if (!inc_ls && out_ls) - path_builder.appendNew<Geom::LineSegment>(outgoing.finalPoint()); - else + // Add outgoing + if (arc2) { + path_builder.append(*arc2); path_builder.append(outgoing); + } else { + // Straight line segment: + path_builder.appendNew<Geom::LineSegment>(outgoing.finalPoint()); + } + + delete arc1; + delete arc2; + } void join_inside(Geom::Path& res, Geom::Curve const& outgoing) @@ -337,11 +436,7 @@ void outline_helper(Geom::Path& res, Geom::Path const& to_add, double width, dou Geom::Point tang1 = Geom::unitTangentAt(reverse(res.back().toSBasis()), 0.); Geom::Point tang2 = Geom::unitTangentAt(to_add.front().toSBasis(), 0.); - // Geom::Point discontinuity_vec = to_add.initialPoint() - res.finalPoint(); bool on_outside = (Geom::cross(tang1, tang2) < 0); - // std::cout << std::fixed << std::setprecision(3) - // << " in: " << tang1 << " out: " << tang2 - // << " side: " << (on_outside?"inside":"outside") << std::endl; if (on_outside) { join_func *jf; diff --git a/src/trace/potrace/auxiliary.h b/src/trace/potrace/auxiliary.h index b7480bbb8..dbf124d7c 100644 --- a/src/trace/potrace/auxiliary.h +++ b/src/trace/potrace/auxiliary.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -8,6 +8,8 @@ #ifndef AUXILIARY_H #define AUXILIARY_H +#include <stdlib.h> + #ifdef HAVE_CONFIG_H #include "config.h" #endif @@ -75,31 +77,4 @@ static inline int floordiv(int a, int n) { #define sq(a) ((a)*(a)) #define cu(a) ((a)*(a)*(a)) -/* ---------------------------------------------------------------------- */ -/* deterministically and efficiently hash (x,y) into a pseudo-random bit */ -static inline int detrand(int x, int y) { - unsigned int z; - static const unsigned char t[256] = { - /* non-linear sequence: constant term of inverse in GF(8), - mod x^8+x^4+x^3+x+1 */ - 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, - 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, - 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, - 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, - 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, - 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, - 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, - 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, - 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, - 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, - 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, - }; - - /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible - 5-bit sequence */ - z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93; - z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff]; - return z; -} - #endif /* AUXILIARY_H */ diff --git a/src/trace/potrace/bitmap.h b/src/trace/potrace/bitmap.h index 2df04b46f..086bbb046 100644 --- a/src/trace/potrace/bitmap.h +++ b/src/trace/potrace/bitmap.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -7,6 +7,7 @@ #include <string.h> #include <stdlib.h> +#include <errno.h> /* The bitmap type is defined in potracelib.h */ #include "potracelib.h" @@ -27,7 +28,7 @@ /* macros for accessing pixel at index (x,y). U* macros omit the bounds check. */ -#define bm_scanline(bm, y) ((bm)->map + (y)*(bm)->dy) +#define bm_scanline(bm, y) ((bm)->map + (ssize_t)(y)*(ssize_t)(bm)->dy) #define bm_index(bm, x, y) (&bm_scanline(bm, y)[(x)/BM_WORDBITS]) #define bm_mask(x) (BM_HIBIT >> ((x) & (BM_WORDBITS-1))) #define bm_range(x, a) ((int)(x) >= 0 && (int)(x) < (a)) @@ -51,10 +52,18 @@ static inline void bm_free(potrace_bitmap_t *bm) { free(bm); } -/* return new un-initialized bitmap. NULL with errno on error */ +/* return new un-initialized bitmap. NULL with errno on error. + Assumes w, h >= 0. */ static inline potrace_bitmap_t *bm_new(int w, int h) { potrace_bitmap_t *bm; - int dy = (w + BM_WORDBITS - 1) / BM_WORDBITS; + int dy = w == 0 ? 0 : (w - 1) / BM_WORDBITS + 1; + ssize_t size = (ssize_t)dy * (ssize_t)h * (ssize_t)BM_WORDSIZE; + + /* check for overflow error */ + if (size < 0 || size / h / dy != BM_WORDSIZE) { + errno = ENOMEM; + return NULL; + } bm = (potrace_bitmap_t *) malloc(sizeof(potrace_bitmap_t)); if (!bm) { @@ -63,7 +72,7 @@ static inline potrace_bitmap_t *bm_new(int w, int h) { bm->w = w; bm->h = h; bm->dy = dy; - bm->map = (potrace_word *) malloc(dy * h * BM_WORDSIZE); + bm->map = (potrace_word *) malloc(size); if (!bm->map) { free(bm); return NULL; @@ -73,23 +82,29 @@ static inline potrace_bitmap_t *bm_new(int w, int h) { /* clear the given bitmap. Set all bits to c. */ static inline void bm_clear(potrace_bitmap_t *bm, int c) { - memset(bm->map, c ? -1 : 0, bm->dy * bm->h * BM_WORDSIZE); + /* Note: if the bitmap was created with bm_new, then it is + guaranteed that size will fit into the ssize_t type. */ + ssize_t size = (ssize_t)bm->dy * (ssize_t)bm->h * (ssize_t)BM_WORDSIZE; + memset(bm->map, c ? -1 : 0, size); } /* duplicate the given bitmap. Return NULL on error with errno set. */ static inline potrace_bitmap_t *bm_dup(const potrace_bitmap_t *bm) { potrace_bitmap_t *bm1 = bm_new(bm->w, bm->h); + ssize_t size = (ssize_t)bm->dy * (ssize_t)bm->h * (ssize_t)BM_WORDSIZE; if (!bm1) { return NULL; } - memcpy(bm1->map, bm->map, bm->dy * bm->h * BM_WORDSIZE); + memcpy(bm1->map, bm->map, size); return bm1; } /* invert the given bitmap. */ static inline void bm_invert(potrace_bitmap_t *bm) { - int i; - for (i = 0; i < bm->dy * bm->h; i++) { + ssize_t i; + ssize_t size = (ssize_t)bm->dy * (ssize_t)bm->h; + + for (i = 0; i < size; i++) { bm->map[i] ^= BM_ALLBITS; } } diff --git a/src/trace/potrace/bitops.h b/src/trace/potrace/bitops.h new file mode 100644 index 000000000..cff734a46 --- /dev/null +++ b/src/trace/potrace/bitops.h @@ -0,0 +1,83 @@ +/* Copyright (C) 2001-2015 Peter Selinger. + This file is part of Potrace. It is free software and it is covered + by the GNU General Public License. See the file COPYING for details. */ + + +/* bits.h: this file defines some macros for bit manipulations. We + provide a generic implementation, as well as machine- and + compiler-specific fast implementations */ + +/* lobit: return the position of the rightmost "1" bit of an int, or + 32 if none. hibit: return 1 + the position of the leftmost "1" bit + of an int, or 0 if none. Note: these functions work on 32-bit + integers. */ + +#ifndef BITOPS_H +#define BITOPS_H + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +/* ---------------------------------------------------------------------- */ +/* machine specific macros */ + +#if defined(HAVE_I386) + +static inline unsigned int lobit(unsigned int x) { + unsigned int res; + asm ("bsf %1,%0\n\t" + "jnz 0f\n\t" + "movl $32,%0\n" + "0:" + : "=r" (res) + : "r" (x) + : "cc"); + return res; +} + +static inline unsigned int hibit(unsigned int x) { + unsigned int res; + + asm ("bsr %1,%0\n\t" + "jnz 0f\n\t" + "movl $-1,%0\n" + "0:" + : "=r" (res) + : "r" (x) + : "cc"); + return res+1; +} + +/* ---------------------------------------------------------------------- */ +#else /* generic macros */ + +static inline unsigned int lobit(unsigned int x) { + unsigned int res = 32; + while (x & 0xffffff) { + x <<= 8; + res -= 8; + } + while (x) { + x <<= 1; + res -= 1; + } + return res; +} + +static inline unsigned int hibit(unsigned int x) { + unsigned int res = 0; + while (x > 0xff) { + x >>= 8; + res += 8; + } + while (x) { + x >>= 1; + res += 1; + } + return res; +} + +#endif + +#endif /* BITOPS_H */ diff --git a/src/trace/potrace/curve.cpp b/src/trace/potrace/curve.cpp index d2e32aa7b..e6a9a4721 100644 --- a/src/trace/potrace/curve.cpp +++ b/src/trace/potrace/curve.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -12,8 +12,8 @@ #include "lists.h" #include "curve.h" -#define SAFE_MALLOC(var, n, typ) \ - if ((var = (typ *)malloc((n)*sizeof(typ))) == NULL) goto malloc_error +#define SAFE_CALLOC(var, n, typ) \ + if ((var = (typ *)calloc(n, sizeof(typ))) == NULL) goto calloc_error /* ---------------------------------------------------------------------- */ /* allocate and free path objects */ @@ -22,14 +22,14 @@ path_t *path_new(void) { path_t *p = NULL; privpath_t *priv = NULL; - SAFE_MALLOC(p, 1, path_t); + SAFE_CALLOC(p, 1, path_t); memset(p, 0, sizeof(path_t)); - SAFE_MALLOC(priv, 1, privpath_t); + SAFE_CALLOC(priv, 1, privpath_t); memset(priv, 0, sizeof(privpath_t)); p->priv = priv; return p; - malloc_error: + calloc_error: free(p); free(priv); return NULL; @@ -81,15 +81,15 @@ typedef dpoint_t dpoint3_t[3]; int privcurve_init(privcurve_t *curve, int n) { memset(curve, 0, sizeof(privcurve_t)); curve->n = n; - SAFE_MALLOC(curve->tag, n, int); - SAFE_MALLOC(curve->c, n, dpoint3_t); - SAFE_MALLOC(curve->vertex, n, dpoint_t); - SAFE_MALLOC(curve->alpha, n, double); - SAFE_MALLOC(curve->alpha0, n, double); - SAFE_MALLOC(curve->beta, n, double); + SAFE_CALLOC(curve->tag, n, int); + SAFE_CALLOC(curve->c, n, dpoint3_t); + SAFE_CALLOC(curve->vertex, n, dpoint_t); + SAFE_CALLOC(curve->alpha, n, double); + SAFE_CALLOC(curve->alpha0, n, double); + SAFE_CALLOC(curve->beta, n, double); return 0; - malloc_error: + calloc_error: free(curve->tag); free(curve->c); free(curve->vertex); diff --git a/src/trace/potrace/curve.h b/src/trace/potrace/curve.h index 6ceae0c3a..feb95b39b 100644 --- a/src/trace/potrace/curve.h +++ b/src/trace/potrace/curve.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/decompose.cpp b/src/trace/potrace/decompose.cpp index 6c27a7ebf..7628b202d 100644 --- a/src/trace/potrace/decompose.cpp +++ b/src/trace/potrace/decompose.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -15,6 +15,33 @@ #include "decompose.h" #include "progress.h" +/* ---------------------------------------------------------------------- */ +/* deterministically and efficiently hash (x,y) into a pseudo-random bit */ + +static inline int detrand(int x, int y) { + unsigned int z; + static const unsigned char t[256] = { + /* non-linear sequence: constant term of inverse in GF(8), + mod x^8+x^4+x^3+x+1 */ + 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, + 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, + 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, + 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, + 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, + 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, + 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, + 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, + 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, + 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, + }; + + /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible + 5-bit sequence */ + z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93; + z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff]; + return z; +} /* ---------------------------------------------------------------------- */ /* auxiliary bitmap manipulations */ diff --git a/src/trace/potrace/decompose.h b/src/trace/potrace/decompose.h index 89b01e504..8ae89b8ad 100644 --- a/src/trace/potrace/decompose.h +++ b/src/trace/potrace/decompose.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/greymap.cpp b/src/trace/potrace/greymap.cpp index e116021c1..4ef2ec8df 100644 --- a/src/trace/potrace/greymap.cpp +++ b/src/trace/potrace/greymap.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -9,8 +9,10 @@ #include <stdlib.h> #include <string.h> #include <math.h> +#include <errno.h> #include "greymap.h" +#include "bitops.h" #define INTBITS (8*sizeof(int)) @@ -22,10 +24,17 @@ static int gm_readbody_bmp(FILE *f, greymap_t **gmp); /* ---------------------------------------------------------------------- */ /* basic greymap routines */ -/* return new un-initialized greymap. NULL with errno on error */ - +/* return new un-initialized greymap. NULL with errno on error. + Assumes w, h >= 0. */ greymap_t *gm_new(int w, int h) { greymap_t *gm; + ssize_t size = (ssize_t)w * (ssize_t)h * (ssize_t)sizeof(signed short int); + + /* check for overflow error */ + if (size < 0 || size / w / h != sizeof(signed short int)) { + errno = ENOMEM; + return NULL; + } gm = (greymap_t *) malloc(sizeof(greymap_t)); if (!gm) { @@ -33,7 +42,7 @@ greymap_t *gm_new(int w, int h) { } gm->w = w; gm->h = h; - gm->map = (signed short int *) malloc(w*h*sizeof(signed short int)); + gm->map = (signed short int *) malloc(size); if (!gm->map) { free(gm); return NULL; @@ -405,6 +414,10 @@ struct bmp_info_s { unsigned int YpixelsPerM; unsigned int ncolors; /* number of colors in palette */ unsigned int ColorsImportant; + unsigned int RedMask; + unsigned int GreenMask; + unsigned int BlueMask; + unsigned int AlphaMask; unsigned int ctbits; /* sample size for color table */ int topdown; /* top-down mode? */ }; @@ -495,6 +508,7 @@ static int gm_readbody_bmp(FILE *f, greymap_t **gmp) { int col[2]; unsigned int bitbuf; unsigned int n; + unsigned int redshift, greenshift, blueshift; gm_read_error = NULL; gm = NULL; @@ -523,12 +537,24 @@ static int gm_readbody_bmp(FILE *f, greymap_t **gmp) { TRY(bmp_readint(f, 4, &bmpinfo.YpixelsPerM)); TRY(bmp_readint(f, 4, &bmpinfo.ncolors)); TRY(bmp_readint(f, 4, &bmpinfo.ColorsImportant)); - if ((signed int)bmpinfo.h < 0) { - bmpinfo.h = -bmpinfo.h; + if (bmpinfo.InfoSize >= 108) { /* V4 and V5 bitmaps */ + TRY(bmp_readint(f, 4, &bmpinfo.RedMask)); + TRY(bmp_readint(f, 4, &bmpinfo.GreenMask)); + TRY(bmp_readint(f, 4, &bmpinfo.BlueMask)); + TRY(bmp_readint(f, 4, &bmpinfo.AlphaMask)); + } + if (bmpinfo.w > 0x7fffffff) { + goto format_error; + } + if (bmpinfo.h > 0x7fffffff) { + bmpinfo.h = (-bmpinfo.h) & 0xffffffff; bmpinfo.topdown = 1; } else { bmpinfo.topdown = 0; } + if (bmpinfo.h > 0x7fffffff) { + goto format_error; + } } else if (bmpinfo.InfoSize == 12) { /* old OS/2 format */ bmpinfo.ctbits = 24; /* sample size in color table */ @@ -543,6 +569,11 @@ static int gm_readbody_bmp(FILE *f, greymap_t **gmp) { goto format_error; } + if (bmpinfo.comp == 3 && bmpinfo.InfoSize < 108) { + /* bitfield feature is only understood with V4 and V5 format */ + goto format_error; + } + /* forward to color table (e.g., if bmpinfo.InfoSize == 64) */ TRY(bmp_forward(f, 14+bmpinfo.InfoSize)); @@ -557,7 +588,7 @@ static int gm_readbody_bmp(FILE *f, greymap_t **gmp) { /* color table, present only if bmpinfo.bits <= 8. */ if (bmpinfo.bits <= 8) { - coltable = (int *) malloc(bmpinfo.ncolors * sizeof(int)); + coltable = (int *) calloc(bmpinfo.ncolors, sizeof(int)); if (!coltable) { goto std_error; } @@ -651,6 +682,22 @@ static int gm_readbody_bmp(FILE *f, greymap_t **gmp) { } break; + case 0x320: /* 32-bit encoding with bitfields */ + redshift = lobit(bmpinfo.RedMask); + greenshift = lobit(bmpinfo.GreenMask); + blueshift = lobit(bmpinfo.BlueMask); + + for (y=0; y<bmpinfo.h; y++) { + bmp_pad_reset(); + for (x=0; x<bmpinfo.w; x++) { + TRY_EOF(bmp_readint(f, bmpinfo.bits/8, &c)); + c = ((c & bmpinfo.RedMask) >> redshift) + ((c & bmpinfo.GreenMask) >> greenshift) + ((c & bmpinfo.BlueMask) >> blueshift); + GM_UPUT(gm, x, ycorr(y), c/3); + } + TRY(bmp_pad(f)); + } + break; + case 0x204: /* 4-bit runlength compressed encoding (RLE4) */ x = 0; y = 0; diff --git a/src/trace/potrace/greymap.h b/src/trace/potrace/greymap.h index 1fb5426c1..8c9db9bbf 100644 --- a/src/trace/potrace/greymap.h +++ b/src/trace/potrace/greymap.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -7,6 +7,7 @@ #define GREYMAP_H #include <stdio.h> +#include <stdlib.h> /* internal format for greymaps. Note: in this format, rows are ordered from bottom to top. The pixels in each row are given from @@ -22,7 +23,7 @@ typedef struct greymap_s greymap_t; /* macros for accessing pixel at index (x,y). Note that the origin is in the *lower* left corner. U* macros omit the bounds check. */ -#define gm_index(gm, x, y) (&(gm)->map[(x)+(y)*(gm)->w]) +#define gm_index(gm, x, y) (&(gm)->map[(x)+(y)*(ssize_t)(gm)->w]) #define gm_safe(gm, x, y) ((int)(x)>=0 && (int)(x)<(gm)->w && (int)(y)>=0 && (int)(y)<(gm)->h) #define gm_bound(x, m) ((x)<0 ? 0 : (x)>=(m) ? (m)-1 : (x)) #define GM_UGET(gm, x, y) (*gm_index(gm, x, y)) diff --git a/src/trace/potrace/lists.h b/src/trace/potrace/lists.h index 078129afc..394262c23 100644 --- a/src/trace/potrace/lists.h +++ b/src/trace/potrace/lists.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/potracelib.cpp b/src/trace/potrace/potracelib.cpp index 0fb835593..b5463d676 100644 --- a/src/trace/potrace/potracelib.cpp +++ b/src/trace/potrace/potracelib.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/potracelib.h b/src/trace/potrace/potracelib.h index cd142a6e1..0a6ddbf1f 100644 --- a/src/trace/potrace/potracelib.h +++ b/src/trace/potrace/potracelib.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/progress.h b/src/trace/potrace/progress.h index 3e1dfb34e..ecc2ba217 100644 --- a/src/trace/potrace/progress.h +++ b/src/trace/potrace/progress.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/render.cpp b/src/trace/potrace/render.cpp index 3c8f79c05..4f44ae6a6 100644 --- a/src/trace/potrace/render.cpp +++ b/src/trace/potrace/render.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -52,7 +52,7 @@ render_t *render_new(greymap_t *gm) { } memset(rm, 0, sizeof(render_t)); rm->gm = gm; - rm->incrow_buf = (int *) malloc(gm->h * sizeof(int)); + rm->incrow_buf = (int *) calloc(gm->h, sizeof(int)); if (!rm->incrow_buf) { free(rm); return NULL; diff --git a/src/trace/potrace/render.h b/src/trace/potrace/render.h index ad600156a..0caaedff6 100644 --- a/src/trace/potrace/render.h +++ b/src/trace/potrace/render.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ diff --git a/src/trace/potrace/trace.cpp b/src/trace/potrace/trace.cpp index f1e88a908..469262b67 100644 --- a/src/trace/potrace/trace.cpp +++ b/src/trace/potrace/trace.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ @@ -21,8 +21,8 @@ #define COS179 -0.999847695156 /* the cosine of 179 degrees */ /* ---------------------------------------------------------------------- */ -#define SAFE_MALLOC(var, n, typ) \ - if ((var = (typ *)malloc((n)*sizeof(typ))) == NULL) goto malloc_error +#define SAFE_CALLOC(var, n, typ) \ + if ((var = (typ *)calloc(n, sizeof(typ))) == NULL) goto calloc_error /* ---------------------------------------------------------------------- */ /* auxiliary functions */ @@ -265,7 +265,7 @@ static int calc_sums(privpath_t *pp) { int i, x, y; int n = pp->len; - SAFE_MALLOC(pp->sums, pp->len+1, sums_t); + SAFE_CALLOC(pp->sums, pp->len+1, sums_t); /* origin */ pp->x0 = pp->pt[0].x; @@ -284,7 +284,7 @@ static int calc_sums(privpath_t *pp) { } return 0; - malloc_error: + calloc_error: return 1; } @@ -331,8 +331,8 @@ static int calc_lon(privpath_t *pp) { point_t dk; /* direction of k-k1 */ int a, b, c, d; - SAFE_MALLOC(pivk, n, int); - SAFE_MALLOC(nc, n, int); + SAFE_CALLOC(pivk, n, int); + SAFE_CALLOC(nc, n, int); /* initialize the nc data structure. Point from each point to the furthest future point to which it is connected by a vertical or @@ -349,7 +349,7 @@ static int calc_lon(privpath_t *pp) { nc[i] = k; } - SAFE_MALLOC(pp->lon, n, int); + SAFE_CALLOC(pp->lon, n, int); /* determine pivot points: for each i, let pivk[i] be the furthest k such that all j with i<j<k lie on a line connecting i,k. */ @@ -458,7 +458,7 @@ static int calc_lon(privpath_t *pp) { free(nc); return 0; - malloc_error: + calloc_error: free(pivk); free(nc); return 1; @@ -537,12 +537,12 @@ static int bestpolygon(privpath_t *pp) double best; int c; - SAFE_MALLOC(pen, n+1, double); - SAFE_MALLOC(prev, n+1, int); - SAFE_MALLOC(clip0, n, int); - SAFE_MALLOC(clip1, n+1, int); - SAFE_MALLOC(seg0, n+1, int); - SAFE_MALLOC(seg1, n+1, int); + SAFE_CALLOC(pen, n+1, double); + SAFE_CALLOC(prev, n+1, int); + SAFE_CALLOC(clip0, n, int); + SAFE_CALLOC(clip1, n+1, int); + SAFE_CALLOC(seg0, n+1, int); + SAFE_CALLOC(seg1, n+1, int); /* calculate clipped paths */ for (i=0; i<n; i++) { @@ -604,7 +604,7 @@ static int bestpolygon(privpath_t *pp) } pp->m = m; - SAFE_MALLOC(pp->po, m, int); + SAFE_CALLOC(pp->po, m, int); /* read off shortest path */ for (i=n, j=m-1; i>0; j--) { @@ -620,7 +620,7 @@ static int bestpolygon(privpath_t *pp) free(seg1); return 0; - malloc_error: + calloc_error: free(pen); free(prev); free(clip0); @@ -655,13 +655,13 @@ static int adjust_vertices(privpath_t *pp) { dpoint_t s; int r; - SAFE_MALLOC(ctr, m, dpoint_t); - SAFE_MALLOC(dir, m, dpoint_t); - SAFE_MALLOC(q, m, quadform_t); + SAFE_CALLOC(ctr, m, dpoint_t); + SAFE_CALLOC(dir, m, dpoint_t); + SAFE_CALLOC(q, m, quadform_t); r = privcurve_init(&pp->curve, m); if (r) { - goto malloc_error; + goto calloc_error; } /* calculate "optimal" point-slope representation for each line @@ -827,7 +827,7 @@ static int adjust_vertices(privpath_t *pp) { free(q); return 0; - malloc_error: + calloc_error: free(ctr); free(dir); free(q); @@ -875,7 +875,7 @@ static void smooth(privcurve_t *curve, double alphamax) { } curve->alpha0[j] = alpha; /* remember "original" value of alpha */ - if (alpha > alphamax) { /* pointed corner */ + if (alpha >= alphamax) { /* pointed corner */ curve->tag[j] = POTRACE_CORNER; curve->c[j][1] = curve->vertex[j]; curve->c[j][2] = p4; @@ -1075,12 +1075,12 @@ static int opticurve(privpath_t *pp, double opttolerance) { int *convc = NULL; /* conv[m]: pre-computed convexities */ double *areac = NULL; /* cumarea[m+1]: cache for fast area computation */ - SAFE_MALLOC(pt, m+1, int); - SAFE_MALLOC(pen, m+1, double); - SAFE_MALLOC(len, m+1, int); - SAFE_MALLOC(opt, m+1, opti_t); - SAFE_MALLOC(convc, m, int); - SAFE_MALLOC(areac, m+1, double); + SAFE_CALLOC(pt, m+1, int); + SAFE_CALLOC(pen, m+1, double); + SAFE_CALLOC(len, m+1, int); + SAFE_CALLOC(opt, m+1, opti_t); + SAFE_CALLOC(convc, m, int); + SAFE_CALLOC(areac, m+1, double); /* pre-calculate convexity: +1 = right turn, -1 = left turn, 0 = corner */ for (i=0; i<m; i++) { @@ -1134,10 +1134,10 @@ static int opticurve(privpath_t *pp, double opttolerance) { om = len[m]; r = privcurve_init(&pp->ocurve, om); if (r) { - goto malloc_error; + goto calloc_error; } - SAFE_MALLOC(s, om, double); - SAFE_MALLOC(t, om, double); + SAFE_CALLOC(s, om, double); + SAFE_CALLOC(t, om, double); j = m; for (i=om-1; i>=0; i--) { @@ -1182,7 +1182,7 @@ static int opticurve(privpath_t *pp, double opttolerance) { free(areac); return 0; - malloc_error: + calloc_error: free(pt); free(pen); free(len); diff --git a/src/trace/potrace/trace.h b/src/trace/potrace/trace.h index dc2b9247a..c53cdd10f 100644 --- a/src/trace/potrace/trace.h +++ b/src/trace/potrace/trace.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2001-2011 Peter Selinger. +/* Copyright (C) 2001-2015 Peter Selinger. This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ |
