Merge lp:~valavanisalex/inkscape/fix-1156664 into lp:~inkscape.dev/inkscape/trunk

Proposed by Alex Valavanis on 2015-11-12
Status: Merged
Merged at revision: 14480
Proposed branch: lp:~valavanisalex/inkscape/fix-1156664
Merge into: lp:~inkscape.dev/inkscape/trunk
Diff against target: 5061 lines (+276/-4099)
40 files modified
CMakeLists.txt (+0/-1)
CMakeScripts/DefineDependsandFlags.cmake (+11/-0)
CMakeScripts/Modules/FindPotrace.cmake (+62/-0)
configure.ac (+12/-0)
src/menus-skeleton.h (+9/-1)
src/shortcuts.cpp (+8/-1)
src/trace/CMakeLists.txt (+3/-17)
src/trace/Makefile_insert (+5/-16)
src/trace/potrace/auxiliary.h (+0/-80)
src/trace/potrace/bitmap.h (+9/-8)
src/trace/potrace/bitops.h (+0/-83)
src/trace/potrace/curve.cpp (+0/-108)
src/trace/potrace/curve.h (+0/-77)
src/trace/potrace/decompose.cpp (+0/-511)
src/trace/potrace/decompose.h (+0/-16)
src/trace/potrace/greymap.cpp (+0/-941)
src/trace/potrace/greymap.h (+0/-58)
src/trace/potrace/inkscape-potrace.cpp (+3/-4)
src/trace/potrace/inkscape-potrace.h (+1/-1)
src/trace/potrace/lists.h (+0/-285)
src/trace/potrace/potracelib.cpp (+0/-128)
src/trace/potrace/potracelib.h (+0/-139)
src/trace/potrace/progress.h (+0/-77)
src/trace/potrace/render.cpp (+0/-243)
src/trace/potrace/render.h (+0/-27)
src/trace/potrace/trace.cpp (+0/-1245)
src/trace/potrace/trace.h (+0/-15)
src/ui/CMakeLists.txt (+11/-4)
src/ui/dialog/Makefile_insert (+8/-2)
src/ui/dialog/dialog-manager.cpp (+13/-1)
src/ui/dialog/inkscape-preferences.cpp (+2/-0)
src/ui/dialog/inkscape-preferences.h (+8/-0)
src/ui/tool-factory.cpp (+7/-1)
src/ui/tools-switch.h (+8/-0)
src/ui/tools/Makefile_insert (+8/-2)
src/verbs.cpp (+41/-2)
src/verbs.h (+16/-0)
src/widgets/CMakeLists.txt (+9/-2)
src/widgets/Makefile_insert (+8/-2)
src/widgets/toolbox.cpp (+14/-1)
To merge this branch: bzr merge lp:~valavanisalex/inkscape/fix-1156664
Reviewer Review Type Date Requested Status
Inkscape Developers 2015-11-12 Pending
Review via email: mp+277406@code.launchpad.net

Description of the change

This branch removes the embedded copy of Potrace (except for the handy bitmap.h macros) and links to an external installation instead.

I've also allowed Inkscape to build without Potrace being present, so this can be applied (hopefully) independently of the DevLibs update. If Potrace is not found on the user's system, then the flood and trace tools are disabled.

I've tested on Ubuntu 15.10 with and without Potrace, and using either Autotools or CMake.

I'd appreciate someone checking:
(a) does this work on Windows and OS X?
(b) is my CMake implementation sensible?

To post a comment you must log in.
su_v (suv-lp) wrote :

On 2015-11-13 24:49 (+0100), Alex Valavanis wrote:
> I've tested on Ubuntu 15.10 with and without Potrace, and using
> either Autotools or CMake.
>
> I'd appreciate someone checking:
> (a) does this work on Windows and OS X?

Tested successfully with trunk r14478 (GTK2) on OS X 10.7.5 with and
without Potrace, for Autotools- as well as CMake-based build system. Not
tested specifically with osx packaging (it should not cause issues there
though - the external linked library will be copied automagically into
the app bundle, and the library paths rewritten).

Uninformed question wrt potrace: I noticed that in MacPorts (package
manager for OS X) potrace's configure options for metric units
(--enable-metric) and default page size (--enable-a4) are offered as
variants - are these only relevant for the command line tools installed
by potrace, or would different defaults somehow affect trace mode /
flood fill in Inkscape?

> (b) is my CMake implementation sensible?

I noticed that cmake does not inform the user if potrace is not found
(it does report it if found though). Maybe let users know if features
are disabled due to missing optional dependencies?

(c) Independent of build system: it might be safer to disable the
related verbs too (tool, dialog), if compiling without potrace: inkscape
e.g. crashes if launched with one of the (defunct) verbs on the command
line:

$ inkscape --verb=ToolPaintBucket

or when switching tools using keyboard shortcuts (Shift+F7).

14456. By Alex Valavanis on 2015-11-21

Hide unused verbs if Potrace is not available

Alex Valavanis (valavanisalex) wrote :

(c) Hopefully fixed in r14456: The impossible verbs are disabled if Potrace is not found

Alex Valavanis (valavanisalex) wrote :

(a) Yes, these options (AFAIU) are only used for the Potrace command-line application. In Inkscape, we just use the API function that converts a bitmap (i.e., an array of pixels rather than a drawing in real-world units) into vector objects using the same scale.

14457. By Alex Valavanis on 2015-11-21

Add warning about missing Potrace to CMake build

Alex Valavanis (valavanisalex) wrote :

(b) Added a warning about missing Potrace to the CMake build in r14457

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
=== modified file 'CMakeLists.txt'
--- CMakeLists.txt 2015-10-26 22:50:52 +0000
+++ CMakeLists.txt 2015-11-21 12:39:21 +0000
@@ -100,7 +100,6 @@
100# -----------------------------------------------------------------------------100# -----------------------------------------------------------------------------
101# BAD HACKS, NEED TO INVESTIGATE MAKING THESE LESS BAD101# BAD HACKS, NEED TO INVESTIGATE MAKING THESE LESS BAD
102add_definitions(-D_FORTIFY_SOURCE=2)102add_definitions(-D_FORTIFY_SOURCE=2)
103add_definitions(-DPOTRACE="potrace")
104add_definitions(-DORBIT2=1)103add_definitions(-DORBIT2=1)
105add_definitions(-DHAVE_CONFIG_H)104add_definitions(-DHAVE_CONFIG_H)
106add_definitions(-DHAVE_CAIRO_PDF=1) # needed for src/libnrtype/Layout-TNG.h105add_definitions(-DHAVE_CAIRO_PDF=1) # needed for src/libnrtype/Layout-TNG.h
107106
=== modified file 'CMakeScripts/DefineDependsandFlags.cmake'
--- CMakeScripts/DefineDependsandFlags.cmake 2015-10-26 22:50:52 +0000
+++ CMakeScripts/DefineDependsandFlags.cmake 2015-11-21 12:39:21 +0000
@@ -197,6 +197,17 @@
197list(APPEND INKSCAPE_LIBS ${POPT_LIBRARIES})197list(APPEND INKSCAPE_LIBS ${POPT_LIBRARIES})
198add_definitions(${POPT_DEFINITIONS})198add_definitions(${POPT_DEFINITIONS})
199199
200find_package(Potrace)
201if(POTRACE_FOUND)
202 list(APPEND INKSCAPE_INCS_SYS ${POTRACE_INCLUDE_DIRS})
203 list(APPEND INKSCAPE_LIBS ${POTRACE_LIBRARIES})
204 set(HAVE_POTRACE ON)
205 add_definitions(-DHAVE_POTRACE)
206else(POTRACE_FOUND)
207 set(HAVE_POTRACE OFF)
208 message(STATUS "Could not locate the Potrace library headers: the Trace Bitmap and Paintbucket tools will be disabled")
209endif()
210
200if(WITH_DBUS)211if(WITH_DBUS)
201 find_package(DBus REQUIRED)212 find_package(DBus REQUIRED)
202 if(DBUS_FOUND)213 if(DBUS_FOUND)
203214
=== added file 'CMakeScripts/Modules/FindPotrace.cmake'
--- CMakeScripts/Modules/FindPotrace.cmake 1970-01-01 00:00:00 +0000
+++ CMakeScripts/Modules/FindPotrace.cmake 2015-11-21 12:39:21 +0000
@@ -0,0 +1,62 @@
1# POTRACE_FOUND - system has Potrace
2# POTRACE_INCLUDE_DIRS - the Potrace include directory
3# POTRACE_LIBRARIES - The libraries needed to use Potrace
4
5IF (POTRACE_LIBRARIES AND POTRACE_INCLUDE_DIRS)
6 # in cache already
7 SET(POTRACE_FOUND TRUE)
8ELSE (POTRACE_LIBRARIES AND POTRACE_INCLUDE_DIRS)
9 FIND_PATH (POTRACE_INCLUDE_DIR
10 NAMES
11 potracelib.h
12 PATHS
13 /usr/include
14 /usr/local/include
15 $ENV{DEVLIBS_PATH}/include
16 PATH_SUFFIXES
17 potrace
18 )
19
20 FIND_LIBRARY (POTRACE_LIBRARY
21 NAMES
22 potrace
23 libpotrace
24 PATHS
25 /usr/lib
26 /usr/local/lib
27 $ENV{DEVLIBS_PATH}/lib
28 )
29
30 if (POTRACE_LIBRARY)
31 set (POTRACE_FOUND TRUE)
32 endif (POTRACE_LIBRARY)
33
34 set (POTRACE_INCLUDE_DIRS
35 ${POTRACE_INCLUDE_DIR}
36 )
37
38 if (POTRACE_FOUND)
39 set(POTRACE_LIBRARIES
40 ${POTRACE_LIBRARIES}
41 ${POTRACE_LIBRARY}
42 )
43 endif (POTRACE_FOUND)
44
45 if (POTRACE_INCLUDE_DIRS AND POTRACE_LIBRARIES)
46 set(POTRACE_FOUND TRUE)
47 endif (POTRACE_INCLUDE_DIRS AND POTRACE_LIBRARIES)
48
49 if (POTRACE_FOUND)
50 if (NOT Potrace_FIND_QUIETLY)
51 message(STATUS "Found Potrace: ${POTRACE_LIBRARIES}")
52 endif (NOT Potrace_FIND_QUIETLY)
53 else (POTRACE_FOUND)
54 if (Potrace_FIND_REQUIRED)
55 message(FATAL_ERROR "Could not find potrace")
56 endif (Potrace_FIND_REQUIRED)
57 endif (POTRACE_FOUND)
58
59 # show the POTRACE_INCLUDE_DIRS and POTRACE_LIBRARIES variables only in the advanced view
60 MARK_AS_ADVANCED(POTRACE_INCLUDE_DIRS POTRACE_LIBRARIES)
61
62endif (POTRACE_LIBRARIES AND POTRACE_INCLUDE_DIRS)
063
=== modified file 'configure.ac'
--- configure.ac 2015-08-23 07:03:34 +0000
+++ configure.ac 2015-11-21 12:39:21 +0000
@@ -240,6 +240,17 @@
240 AC_DEFINE(HAVE_OPENMP, 1, [Use OpenMP])240 AC_DEFINE(HAVE_OPENMP, 1, [Use OpenMP])
241fi241fi
242242
243dnl ********************
244dnl Check for libpotrace
245dnl ********************
246AC_CHECK_LIB(potrace, potrace_trace, [AC_CHECK_HEADER(potracelib.h, potrace_ok=yes, potrace_ok=no)], potrace_ok=no)
247if test "x$potrace_ok" = "xyes"; then
248 LIBS="-lpotrace $LIBS"
249 AC_DEFINE(HAVE_POTRACE, 1, [Use Potrace])
250fi
251
252AM_CONDITIONAL(HAVE_POTRACE, test "x$potrace_ok" = "xyes")
253
243dnl ******************************254dnl ******************************
244dnl Check for libexif255dnl Check for libexif
245dnl ******************************256dnl ******************************
@@ -1192,6 +1203,7 @@
1192 Enable LittleCms: ${enable_lcms}1203 Enable LittleCms: ${enable_lcms}
1193 Enable DBUS: ${with_dbus} 1204 Enable DBUS: ${with_dbus}
1194 Enable Poppler-Cairo: ${enable_poppler_cairo}1205 Enable Poppler-Cairo: ${enable_poppler_cairo}
1206 Enable Potrace: ${potrace_ok}
1195 ImageMagick Magick++: ${magick_ok}1207 ImageMagick Magick++: ${magick_ok}
1196 Libwpg: ${with_libwpg}1208 Libwpg: ${with_libwpg}
1197 Libvisio: ${with_libvisio}1209 Libvisio: ${with_libvisio}
11981210
=== modified file 'src/menus-skeleton.h'
--- src/menus-skeleton.h 2015-01-25 11:26:05 +0000
+++ src/menus-skeleton.h 2015-11-21 12:39:21 +0000
@@ -1,7 +1,9 @@
1#ifndef SEEN_MENUS_SKELETON_H1#ifndef SEEN_MENUS_SKELETON_H
2#define SEEN_MENUS_SKELETON_H2#define SEEN_MENUS_SKELETON_H
33
4#include "config.h"4#ifdef HAVE_CONFIG_H
5# include "config.h"
6#endif
57
6#ifdef __cplusplus8#ifdef __cplusplus
7#undef N_9#undef N_
@@ -221,7 +223,11 @@
221" <submenu name=\"" N_("_Path") "\">\n"223" <submenu name=\"" N_("_Path") "\">\n"
222" <verb verb-id=\"ObjectToPath\" />\n"224" <verb verb-id=\"ObjectToPath\" />\n"
223" <verb verb-id=\"StrokeToPath\" />\n"225" <verb verb-id=\"StrokeToPath\" />\n"
226
227#if HAVE_POTRACE
224" <verb verb-id=\"SelectionTrace\" />\n"228" <verb verb-id=\"SelectionTrace\" />\n"
229#endif
230
225" <verb verb-id=\"SelectionPixelArt\" />\n"231" <verb verb-id=\"SelectionPixelArt\" />\n"
226" <separator/>\n"232" <separator/>\n"
227" <verb verb-id=\"SelectionUnion\" />\n"233" <verb verb-id=\"SelectionUnion\" />\n"
@@ -284,7 +290,9 @@
284" <verb verb-id=\"TutorialsBasic\" />\n"290" <verb verb-id=\"TutorialsBasic\" />\n"
285" <verb verb-id=\"TutorialsShapes\" />\n"291" <verb verb-id=\"TutorialsShapes\" />\n"
286" <verb verb-id=\"TutorialsAdvanced\" />\n"292" <verb verb-id=\"TutorialsAdvanced\" />\n"
293#if HAVE_POTRACE
287" <verb verb-id=\"TutorialsTracing\" />\n"294" <verb verb-id=\"TutorialsTracing\" />\n"
295#endif
288" <verb verb-id=\"TutorialsTracingPixelArt\" />\n"296" <verb verb-id=\"TutorialsTracingPixelArt\" />\n"
289" <verb verb-id=\"TutorialsCalligraphy\" />\n"297" <verb verb-id=\"TutorialsCalligraphy\" />\n"
290" <verb verb-id=\"TutorialsInterpolate\" />\n"298" <verb verb-id=\"TutorialsInterpolate\" />\n"
291299
=== modified file 'src/shortcuts.cpp'
--- src/shortcuts.cpp 2014-06-26 19:40:39 +0000
+++ src/shortcuts.cpp 2015-11-21 12:39:21 +0000
@@ -575,7 +575,14 @@
575 }575 }
576576
577 Inkscape::Verb *verb=Inkscape::Verb::getbyid(verb_name);577 Inkscape::Verb *verb=Inkscape::Verb::getbyid(verb_name);
578 if (!verb) {578 if (!verb
579#if !HAVE_POTRACE
580 // Squash warning about disabled features
581 && strcmp(verb_name, "ToolPaintBucket") != 0
582 && strcmp(verb_name, "SelectionTrace") != 0
583 && strcmp(verb_name, "PaintBucketPrefs") != 0
584#endif
585 ) {
579 g_warning("Unknown verb name: %s", verb_name);586 g_warning("Unknown verb name: %s", verb_name);
580 continue;587 continue;
581 }588 }
582589
=== modified file 'src/trace/CMakeLists.txt'
--- src/trace/CMakeLists.txt 2015-06-08 19:01:23 +0000
+++ src/trace/CMakeLists.txt 2015-11-21 12:39:21 +0000
@@ -1,3 +1,4 @@
1if (${HAVE_POTRACE})
12
2set(trace_SRC3set(trace_SRC
3 filterset.cpp4 filterset.cpp
@@ -7,14 +8,7 @@
7 siox.cpp8 siox.cpp
8 trace.cpp9 trace.cpp
910
10 potrace/curve.cpp
11 potrace/decompose.cpp
12 potrace/greymap.cpp
13 potrace/inkscape-potrace.cpp11 potrace/inkscape-potrace.cpp
14 potrace/potracelib.cpp
15 potrace/render.cpp
16 potrace/trace.cpp
17
1812
19 # -------13 # -------
20 # Headers14 # Headers
@@ -26,19 +20,11 @@
26 siox.h20 siox.h
27 trace.h21 trace.h
2822
29 potrace/auxiliary.h
30 potrace/bitmap.h23 potrace/bitmap.h
31 potrace/bitops.h
32 potrace/curve.h
33 potrace/decompose.h
34 potrace/greymap.h
35 potrace/inkscape-potrace.h24 potrace/inkscape-potrace.h
36 potrace/lists.h
37 potrace/potracelib.h
38 potrace/progress.h
39 potrace/render.h
40 potrace/trace.h
41)25)
4226
43# add_inkscape_lib(trace_LIB "${trace_SRC}")27# add_inkscape_lib(trace_LIB "${trace_SRC}")
44add_inkscape_source("${trace_SRC}")28add_inkscape_source("${trace_SRC}")
29
30endif()
4531
=== modified file 'src/trace/Makefile_insert'
--- src/trace/Makefile_insert 2009-02-20 22:15:27 +0000
+++ src/trace/Makefile_insert 2015-11-21 12:39:21 +0000
@@ -1,5 +1,7 @@
1## Makefile.am fragment sourced by src/Makefile.am.1## Makefile.am fragment sourced by src/Makefile.am.
22
3if HAVE_POTRACE
4
3ink_common_sources += \5ink_common_sources += \
4 trace/pool.h \6 trace/pool.h \
5 trace/trace.h \7 trace/trace.h \
@@ -14,21 +16,8 @@
14 trace/filterset.cpp \16 trace/filterset.cpp \
15 trace/siox.h \17 trace/siox.h \
16 trace/siox.cpp \18 trace/siox.cpp \
17 trace/potrace/auxiliary.h \19 trace/potrace/bitmap.h \
18 trace/potrace/bitmap.h \
19 trace/potrace/curve.cpp \
20 trace/potrace/curve.h \
21 trace/potrace/decompose.cpp \
22 trace/potrace/decompose.h \
23 trace/potrace/greymap.cpp \
24 trace/potrace/greymap.h \
25 trace/potrace/lists.h \
26 trace/potrace/potracelib.cpp \
27 trace/potrace/potracelib.h \
28 trace/potrace/progress.h \
29 trace/potrace/render.cpp \
30 trace/potrace/render.h \
31 trace/potrace/trace.cpp \
32 trace/potrace/trace.h \
33 trace/potrace/inkscape-potrace.cpp \20 trace/potrace/inkscape-potrace.cpp \
34 trace/potrace/inkscape-potrace.h21 trace/potrace/inkscape-potrace.h
22
23endif
3524
=== removed file 'src/trace/potrace/auxiliary.h'
--- src/trace/potrace/auxiliary.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/auxiliary.h 1970-01-01 00:00:00 +0000
@@ -1,80 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5/* This header file collects some general-purpose macros (and static
6 inline functions) that are used in various places. */
7
8#ifndef AUXILIARY_H
9#define AUXILIARY_H
10
11#include <stdlib.h>
12
13#ifdef HAVE_CONFIG_H
14#include "config.h"
15#endif
16
17/* ---------------------------------------------------------------------- */
18/* point arithmetic */
19
20#include "potracelib.h"
21
22struct point_s {
23 long x;
24 long y;
25};
26typedef struct point_s point_t;
27
28typedef potrace_dpoint_t dpoint_t;
29
30/* convert point_t to dpoint_t */
31static inline dpoint_t dpoint(point_t p) {
32 dpoint_t res;
33 res.x = p.x;
34 res.y = p.y;
35 return res;
36}
37
38/* range over the straight line segment [a,b] when lambda ranges over [0,1] */
39static inline dpoint_t interval(double lambda, dpoint_t a, dpoint_t b) {
40 dpoint_t res;
41
42 res.x = a.x + lambda * (b.x - a.x);
43 res.y = a.y + lambda * (b.y - a.y);
44 return res;
45}
46
47/* ---------------------------------------------------------------------- */
48/* some useful macros. Note: the "mod" macro works correctly for
49 negative a. Also note that the test for a>=n, while redundant,
50 speeds up the mod function by 70% in the average case (significant
51 since the program spends about 16% of its time here - or 40%
52 without the test). The "floordiv" macro returns the largest integer
53 <= a/n, and again this works correctly for negative a, as long as
54 a,n are integers and n>0. */
55
56/* integer arithmetic */
57
58static inline int mod(int a, int n) {
59 return a>=n ? a%n : a>=0 ? a : n-1-(-1-a)%n;
60}
61
62static inline int floordiv(int a, int n) {
63 return a>=0 ? a/n : -1-(-1-a)/n;
64}
65
66/* Note: the following work for integers and other numeric types. */
67#undef sign
68#undef abs
69#undef min
70#undef max
71#undef sq
72#undef cu
73#define sign(x) ((x)>0 ? 1 : (x)<0 ? -1 : 0)
74#define abs(a) ((a)>0 ? (a) : -(a))
75#define min(a,b) ((a)<(b) ? (a) : (b))
76#define max(a,b) ((a)>(b) ? (a) : (b))
77#define sq(a) ((a)*(a))
78#define cu(a) ((a)*(a)*(a))
79
80#endif /* AUXILIARY_H */
810
=== modified file 'src/trace/potrace/bitmap.h'
--- src/trace/potrace/bitmap.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/bitmap.h 2015-11-21 12:39:21 +0000
@@ -8,6 +8,7 @@
8#include <string.h>8#include <string.h>
9#include <stdlib.h>9#include <stdlib.h>
10#include <errno.h>10#include <errno.h>
11#include <stddef.h>
1112
12/* The bitmap type is defined in potracelib.h */13/* The bitmap type is defined in potracelib.h */
13#include "potracelib.h"14#include "potracelib.h"
@@ -28,7 +29,7 @@
28/* macros for accessing pixel at index (x,y). U* macros omit the29/* macros for accessing pixel at index (x,y). U* macros omit the
29 bounds check. */30 bounds check. */
3031
31#define bm_scanline(bm, y) ((bm)->map + (ssize_t)(y)*(ssize_t)(bm)->dy)32#define bm_scanline(bm, y) ((bm)->map + (ptrdiff_t)(y)*(ptrdiff_t)(bm)->dy)
32#define bm_index(bm, x, y) (&bm_scanline(bm, y)[(x)/BM_WORDBITS])33#define bm_index(bm, x, y) (&bm_scanline(bm, y)[(x)/BM_WORDBITS])
33#define bm_mask(x) (BM_HIBIT >> ((x) & (BM_WORDBITS-1)))34#define bm_mask(x) (BM_HIBIT >> ((x) & (BM_WORDBITS-1)))
34#define bm_range(x, a) ((int)(x) >= 0 && (int)(x) < (a))35#define bm_range(x, a) ((int)(x) >= 0 && (int)(x) < (a))
@@ -57,10 +58,10 @@
57static inline potrace_bitmap_t *bm_new(int w, int h) {58static inline potrace_bitmap_t *bm_new(int w, int h) {
58 potrace_bitmap_t *bm;59 potrace_bitmap_t *bm;
59 int dy = w == 0 ? 0 : (w - 1) / BM_WORDBITS + 1;60 int dy = w == 0 ? 0 : (w - 1) / BM_WORDBITS + 1;
60 ssize_t size = (ssize_t)dy * (ssize_t)h * (ssize_t)BM_WORDSIZE;61 ptrdiff_t size = (ptrdiff_t)dy * (ptrdiff_t)h * (ptrdiff_t)BM_WORDSIZE;
6162
62 /* check for overflow error */63 /* check for overflow error */
63 if (size < 0 || size / h / dy != BM_WORDSIZE) {64 if (size < 0 || (h != 0 && dy != 0 && size / h / dy != BM_WORDSIZE)) {
64 errno = ENOMEM;65 errno = ENOMEM;
65 return NULL;66 return NULL;
66 }67 }
@@ -83,15 +84,15 @@
83/* clear the given bitmap. Set all bits to c. */84/* clear the given bitmap. Set all bits to c. */
84static inline void bm_clear(potrace_bitmap_t *bm, int c) {85static inline void bm_clear(potrace_bitmap_t *bm, int c) {
85 /* Note: if the bitmap was created with bm_new, then it is86 /* Note: if the bitmap was created with bm_new, then it is
86 guaranteed that size will fit into the ssize_t type. */87 guaranteed that size will fit into the ptrdiff_t type. */
87 ssize_t size = (ssize_t)bm->dy * (ssize_t)bm->h * (ssize_t)BM_WORDSIZE;88 ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h * (ptrdiff_t)BM_WORDSIZE;
88 memset(bm->map, c ? -1 : 0, size);89 memset(bm->map, c ? -1 : 0, size);
89}90}
9091
91/* duplicate the given bitmap. Return NULL on error with errno set. */92/* duplicate the given bitmap. Return NULL on error with errno set. */
92static inline potrace_bitmap_t *bm_dup(const potrace_bitmap_t *bm) {93static inline potrace_bitmap_t *bm_dup(const potrace_bitmap_t *bm) {
93 potrace_bitmap_t *bm1 = bm_new(bm->w, bm->h);94 potrace_bitmap_t *bm1 = bm_new(bm->w, bm->h);
94 ssize_t size = (ssize_t)bm->dy * (ssize_t)bm->h * (ssize_t)BM_WORDSIZE;95 ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h * (ptrdiff_t)BM_WORDSIZE;
95 if (!bm1) {96 if (!bm1) {
96 return NULL;97 return NULL;
97 }98 }
@@ -101,8 +102,8 @@
101102
102/* invert the given bitmap. */103/* invert the given bitmap. */
103static inline void bm_invert(potrace_bitmap_t *bm) {104static inline void bm_invert(potrace_bitmap_t *bm) {
104 ssize_t i;105 ptrdiff_t i;
105 ssize_t size = (ssize_t)bm->dy * (ssize_t)bm->h;106 ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h;
106107
107 for (i = 0; i < size; i++) {108 for (i = 0; i < size; i++) {
108 bm->map[i] ^= BM_ALLBITS;109 bm->map[i] ^= BM_ALLBITS;
109110
=== removed file 'src/trace/potrace/bitops.h'
--- src/trace/potrace/bitops.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/bitops.h 1970-01-01 00:00:00 +0000
@@ -1,83 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6/* bits.h: this file defines some macros for bit manipulations. We
7 provide a generic implementation, as well as machine- and
8 compiler-specific fast implementations */
9
10/* lobit: return the position of the rightmost "1" bit of an int, or
11 32 if none. hibit: return 1 + the position of the leftmost "1" bit
12 of an int, or 0 if none. Note: these functions work on 32-bit
13 integers. */
14
15#ifndef BITOPS_H
16#define BITOPS_H
17
18#ifdef HAVE_CONFIG_H
19#include "config.h"
20#endif
21
22/* ---------------------------------------------------------------------- */
23/* machine specific macros */
24
25#if defined(HAVE_I386)
26
27static inline unsigned int lobit(unsigned int x) {
28 unsigned int res;
29 asm ("bsf %1,%0\n\t"
30 "jnz 0f\n\t"
31 "movl $32,%0\n"
32 "0:"
33 : "=r" (res)
34 : "r" (x)
35 : "cc");
36 return res;
37}
38
39static inline unsigned int hibit(unsigned int x) {
40 unsigned int res;
41
42 asm ("bsr %1,%0\n\t"
43 "jnz 0f\n\t"
44 "movl $-1,%0\n"
45 "0:"
46 : "=r" (res)
47 : "r" (x)
48 : "cc");
49 return res+1;
50}
51
52/* ---------------------------------------------------------------------- */
53#else /* generic macros */
54
55static inline unsigned int lobit(unsigned int x) {
56 unsigned int res = 32;
57 while (x & 0xffffff) {
58 x <<= 8;
59 res -= 8;
60 }
61 while (x) {
62 x <<= 1;
63 res -= 1;
64 }
65 return res;
66}
67
68static inline unsigned int hibit(unsigned int x) {
69 unsigned int res = 0;
70 while (x > 0xff) {
71 x >>= 8;
72 res += 8;
73 }
74 while (x) {
75 x >>= 1;
76 res += 1;
77 }
78 return res;
79}
80
81#endif
82
83#endif /* BITOPS_H */
840
=== removed file 'src/trace/potrace/curve.cpp'
--- src/trace/potrace/curve.cpp 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/curve.cpp 1970-01-01 00:00:00 +0000
@@ -1,108 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5/* private part of the path and curve data structures */
6
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11#include "potracelib.h"
12#include "lists.h"
13#include "curve.h"
14
15#define SAFE_CALLOC(var, n, typ) \
16 if ((var = (typ *)calloc(n, sizeof(typ))) == NULL) goto calloc_error
17
18/* ---------------------------------------------------------------------- */
19/* allocate and free path objects */
20
21path_t *path_new(void) {
22 path_t *p = NULL;
23 privpath_t *priv = NULL;
24
25 SAFE_CALLOC(p, 1, path_t);
26 memset(p, 0, sizeof(path_t));
27 SAFE_CALLOC(priv, 1, privpath_t);
28 memset(priv, 0, sizeof(privpath_t));
29 p->priv = priv;
30 return p;
31
32 calloc_error:
33 free(p);
34 free(priv);
35 return NULL;
36}
37
38/* free the members of the given curve structure. Leave errno unchanged. */
39static void privcurve_free_members(privcurve_t *curve) {
40 free(curve->tag);
41 free(curve->c);
42 free(curve->vertex);
43 free(curve->alpha);
44 free(curve->alpha0);
45 free(curve->beta);
46}
47
48/* free a path. Leave errno untouched. */
49void path_free(path_t *p) {
50 if (p) {
51 if (p->priv) {
52 free(p->priv->pt);
53 free(p->priv->lon);
54 free(p->priv->sums);
55 free(p->priv->po);
56 privcurve_free_members(&p->priv->curve);
57 privcurve_free_members(&p->priv->ocurve);
58 }
59 free(p->priv);
60 /* do not free p->fcurve ! */
61 }
62 free(p);
63}
64
65/* free a pathlist, leaving errno untouched. */
66void pathlist_free(path_t *plist) {
67 path_t *p;
68
69 list_forall_unlink(p, plist) {
70 path_free(p);
71 }
72}
73
74/* ---------------------------------------------------------------------- */
75/* initialize and finalize curve structures */
76
77typedef dpoint_t dpoint3_t[3];
78
79/* initialize the members of the given curve structure to size m.
80 Return 0 on success, 1 on error with errno set. */
81int privcurve_init(privcurve_t *curve, int n) {
82 memset(curve, 0, sizeof(privcurve_t));
83 curve->n = n;
84 SAFE_CALLOC(curve->tag, n, int);
85 SAFE_CALLOC(curve->c, n, dpoint3_t);
86 SAFE_CALLOC(curve->vertex, n, dpoint_t);
87 SAFE_CALLOC(curve->alpha, n, double);
88 SAFE_CALLOC(curve->alpha0, n, double);
89 SAFE_CALLOC(curve->beta, n, double);
90 return 0;
91
92 calloc_error:
93 free(curve->tag);
94 free(curve->c);
95 free(curve->vertex);
96 free(curve->alpha);
97 free(curve->alpha0);
98 free(curve->beta);
99 return 1;
100}
101
102/* copy private to public curve structure */
103void privcurve_to_curve(privcurve_t *pc, potrace_curve_t *c) {
104 c->n = pc->n;
105 c->tag = pc->tag;
106 c->c = pc->c;
107}
108
1090
=== removed file 'src/trace/potrace/curve.h'
--- src/trace/potrace/curve.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/curve.h 1970-01-01 00:00:00 +0000
@@ -1,77 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5#ifndef CURVE_H
6#define CURVE_H
7
8#include "auxiliary.h"
9
10/* vertex is c[1] for tag=POTRACE_CORNER, and the intersection of
11 .c[-1][2]..c[0] and c[1]..c[2] for tag=POTRACE_CURVETO. alpha is only
12 defined for tag=POTRACE_CURVETO and is the alpha parameter of the curve:
13 .c[-1][2]..c[0] = alpha*(.c[-1][2]..vertex), and
14 c[2]..c[1] = alpha*(c[2]..vertex).
15 Beta is so that (.beta[i])[.vertex[i],.vertex[i+1]] = .c[i][2].
16*/
17
18struct privcurve_s {
19 int n; /* number of segments */
20 int *tag; /* tag[n]: POTRACE_CORNER or POTRACE_CURVETO */
21 dpoint_t (*c)[3]; /* c[n][i]: control points.
22 c[n][0] is unused for tag[n]=POTRACE_CORNER */
23 /* the remainder of this structure is special to privcurve, and is
24 used in EPS debug output and special EPS "short coding". These
25 fields are valid only if "alphacurve" is set. */
26 int alphacurve; /* have the following fields been initialized? */
27 dpoint_t *vertex; /* for POTRACE_CORNER, this equals c[1] */
28 double *alpha; /* only for POTRACE_CURVETO */
29 double *alpha0; /* "uncropped" alpha parameter - for debug output only */
30 double *beta;
31};
32typedef struct privcurve_s privcurve_t;
33
34struct sums_s {
35 double x;
36 double y;
37 double x2;
38 double xy;
39 double y2;
40};
41typedef struct sums_s sums_t;
42
43/* the path structure is filled in with information about a given path
44 as it is accumulated and passed through the different stages of the
45 Potrace algorithm. Backends only need to read the fcurve and fm
46 fields of this data structure, but debugging backends may read
47 other fields. */
48struct potrace_privpath_s {
49 int len;
50 point_t *pt; /* pt[len]: path as extracted from bitmap */
51 int *lon; /* lon[len]: (i,lon[i]) = longest straight line from i */
52
53 int x0, y0; /* origin for sums */
54 sums_t *sums; /* sums[len+1]: cache for fast summing */
55
56 int m; /* length of optimal polygon */
57 int *po; /* po[m]: optimal polygon */
58
59 privcurve_t curve; /* curve[m]: array of curve elements */
60 privcurve_t ocurve; /* ocurve[om]: array of curve elements */
61 privcurve_t *fcurve; /* final curve: this points to either curve or
62 ocurve. Do not free this separately. */
63};
64typedef struct potrace_privpath_s potrace_privpath_t;
65
66/* shorter names */
67typedef potrace_privpath_t privpath_t;
68typedef potrace_path_t path_t;
69
70path_t *path_new(void);
71void path_free(path_t *p);
72void pathlist_free(path_t *plist);
73int privcurve_init(privcurve_t *curve, int n);
74void privcurve_to_curve(privcurve_t *pc, potrace_curve_t *c);
75
76#endif /* CURVE_H */
77
780
=== removed file 'src/trace/potrace/decompose.cpp'
--- src/trace/potrace/decompose.cpp 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/decompose.cpp 1970-01-01 00:00:00 +0000
@@ -1,511 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6#include <stdio.h>
7#include <stdlib.h>
8#include <string.h>
9#include <limits.h>
10
11#include "potracelib.h"
12#include "curve.h"
13#include "lists.h"
14#include "bitmap.h"
15#include "decompose.h"
16#include "progress.h"
17
18/* ---------------------------------------------------------------------- */
19/* deterministically and efficiently hash (x,y) into a pseudo-random bit */
20
21static inline int detrand(int x, int y) {
22 unsigned int z;
23 static const unsigned char t[256] = {
24 /* non-linear sequence: constant term of inverse in GF(8),
25 mod x^8+x^4+x^3+x+1 */
26 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1,
27 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0,
28 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
29 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1,
30 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0,
31 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0,
32 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0,
33 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1,
34 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0,
35 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1,
36 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
37 };
38
39 /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible
40 5-bit sequence */
41 z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93;
42 z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff];
43 return z;
44}
45
46/* ---------------------------------------------------------------------- */
47/* auxiliary bitmap manipulations */
48
49/* set the excess padding to 0 */
50static void bm_clearexcess(potrace_bitmap_t *bm) {
51 if (bm->w % BM_WORDBITS != 0) {
52 potrace_word mask = BM_ALLBITS << (BM_WORDBITS - (bm->w % BM_WORDBITS));
53 for (int y=0; y<bm->h; y++) {
54 *bm_index(bm, bm->w, y) &= mask;
55 }
56 }
57}
58
59struct bbox_s {
60 int x0, x1, y0, y1; /* bounding box */
61};
62typedef struct bbox_s bbox_t;
63
64/* clear the bm, assuming the bounding box is set correctly (faster
65 than clearing the whole bitmap) */
66static void clear_bm_with_bbox(potrace_bitmap_t *bm, bbox_t *bbox) {
67 int imin = (bbox->x0 / BM_WORDBITS);
68 int imax = ((bbox->x1 + BM_WORDBITS-1) / BM_WORDBITS);
69 int i, y;
70
71 for (y=bbox->y0; y<bbox->y1; y++) {
72 for (i=imin; i<imax; i++) {
73 bm_scanline(bm, y)[i] = 0;
74 }
75 }
76}
77
78/* ---------------------------------------------------------------------- */
79/* auxiliary functions */
80
81/* return the "majority" value of bitmap bm at intersection (x,y). We
82 assume that the bitmap is balanced at "radius" 1. */
83static int majority(potrace_bitmap_t *bm, int x, int y) {
84 int i, a, ct;
85
86 for (i=2; i<5; i++) { /* check at "radius" i */
87 ct = 0;
88 for (a=-i+1; a<=i-1; a++) {
89 ct += BM_GET(bm, x+a, y+i-1) ? 1 : -1;
90 ct += BM_GET(bm, x+i-1, y+a-1) ? 1 : -1;
91 ct += BM_GET(bm, x+a-1, y-i) ? 1 : -1;
92 ct += BM_GET(bm, x-i, y+a) ? 1 : -1;
93 }
94 if (ct>0) {
95 return 1;
96 } else if (ct<0) {
97 return 0;
98 }
99 }
100 return 0;
101}
102
103/* ---------------------------------------------------------------------- */
104/* decompose image into paths */
105
106/* efficiently invert bits [x,infty) and [xa,infty) in line y. Here xa
107 must be a multiple of BM_WORDBITS. */
108static void xor_to_ref(potrace_bitmap_t *bm, int x, int y, int xa) {
109 int xhi = x & -BM_WORDBITS;
110 int xlo = x & (BM_WORDBITS-1); /* = x % BM_WORDBITS */
111 int i;
112
113 if (xhi<xa) {
114 for (i = xhi; i < xa; i+=BM_WORDBITS) {
115 *bm_index(bm, i, y) ^= BM_ALLBITS;
116 }
117 } else {
118 for (i = xa; i < xhi; i+=BM_WORDBITS) {
119 *bm_index(bm, i, y) ^= BM_ALLBITS;
120 }
121 }
122 /* note: the following "if" is needed because x86 treats a<<b as
123 a<<(b&31). I spent hours looking for this bug. */
124 if (xlo) {
125 *bm_index(bm, xhi, y) ^= (BM_ALLBITS << (BM_WORDBITS - xlo));
126 }
127}
128
129/* a path is represented as an array of points, which are thought to
130 lie on the corners of pixels (not on their centers). The path point
131 (x,y) is the lower left corner of the pixel (x,y). Paths are
132 represented by the len/pt components of a path_t object (which
133 also stores other information about the path) */
134
135/* xor the given pixmap with the interior of the given path. Note: the
136 path must be within the dimensions of the pixmap. */
137static void xor_path(potrace_bitmap_t *bm, path_t *p) {
138 int xa, x, y, k, y1;
139
140 if (p->priv->len <= 0) { /* a path of length 0 is silly, but legal */
141 return;
142 }
143
144 y1 = p->priv->pt[p->priv->len-1].y;
145
146 xa = p->priv->pt[0].x & -BM_WORDBITS;
147 for (k=0; k<p->priv->len; k++) {
148 x = p->priv->pt[k].x;
149 y = p->priv->pt[k].y;
150
151 if (y != y1) {
152 /* efficiently invert the rectangle [x,xa] x [y,y1] */
153 xor_to_ref(bm, x, min(y,y1), xa);
154 y1 = y;
155 }
156 }
157}
158
159/* Find the bounding box of a given path. Path is assumed to be of
160 non-zero length. */
161static void setbbox_path(bbox_t *bbox, path_t *p) {
162 int x, y;
163 int k;
164
165 bbox->y0 = INT_MAX;
166 bbox->y1 = 0;
167 bbox->x0 = INT_MAX;
168 bbox->x1 = 0;
169
170 for (k=0; k<p->priv->len; k++) {
171 x = p->priv->pt[k].x;
172 y = p->priv->pt[k].y;
173
174 if (x < bbox->x0) {
175 bbox->x0 = x;
176 }
177 if (x > bbox->x1) {
178 bbox->x1 = x;
179 }
180 if (y < bbox->y0) {
181 bbox->y0 = y;
182 }
183 if (y > bbox->y1) {
184 bbox->y1 = y;
185 }
186 }
187}
188
189/* compute a path in the given pixmap, separating black from white.
190 Start path at the point (x0,x1), which must be an upper left corner
191 of the path. Also compute the area enclosed by the path. Return a
192 new path_t object, or NULL on error (note that a legitimate path
193 cannot have length 0). Sign is required for correct interpretation
194 of turnpolicies. */
195static path_t *findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy) {
196 int x, y, dirx, diry, len, size, area;
197 int c, d, tmp;
198 point_t *pt, *pt1;
199 path_t *p = NULL;
200
201 x = x0;
202 y = y0;
203 dirx = 0;
204 diry = -1;
205
206 len = size = 0;
207 pt = NULL;
208 area = 0;
209
210 while (1) {
211 /* add point to path */
212 if (len>=size) {
213 size += 100;
214 size = (int)(1.3 * size);
215 pt1 = (point_t *)realloc(pt, size * sizeof(point_t));
216 if (!pt1) {
217 goto error;
218 }
219 pt = pt1;
220 }
221 pt[len].x = x;
222 pt[len].y = y;
223 len++;
224
225 /* move to next point */
226 x += dirx;
227 y += diry;
228 area += x*diry;
229
230 /* path complete? */
231 if (x==x0 && y==y0) {
232 break;
233 }
234
235 /* determine next direction */
236 c = BM_GET(bm, x + (dirx+diry-1)/2, y + (diry-dirx-1)/2);
237 d = BM_GET(bm, x + (dirx-diry-1)/2, y + (diry+dirx-1)/2);
238
239 if (c && !d) { /* ambiguous turn */
240 if (turnpolicy == POTRACE_TURNPOLICY_RIGHT
241 || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+')
242 || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-')
243 || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand(x,y))
244 || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y))
245 || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) {
246 tmp = dirx; /* right turn */
247 dirx = diry;
248 diry = -tmp;
249 } else {
250 tmp = dirx; /* left turn */
251 dirx = -diry;
252 diry = tmp;
253 }
254 } else if (c) { /* right turn */
255 tmp = dirx;
256 dirx = diry;
257 diry = -tmp;
258 } else if (!d) { /* left turn */
259 tmp = dirx;
260 dirx = -diry;
261 diry = tmp;
262 }
263 } /* while this path */
264
265 /* allocate new path object */
266 p = path_new();
267 if (!p) {
268 goto error;
269 }
270
271 p->priv->pt = pt;
272 p->priv->len = len;
273 p->area = area;
274 p->sign = sign;
275
276 return p;
277
278 error:
279 free(pt);
280 return NULL;
281}
282
283/* Give a tree structure to the given path list, based on "insideness"
284 testing. I.e., path A is considered "below" path B if it is inside
285 path B. The input pathlist is assumed to be ordered so that "outer"
286 paths occur before "inner" paths. The tree structure is stored in
287 the "childlist" and "sibling" components of the path_t
288 structure. The linked list structure is also changed so that
289 negative path components are listed immediately after their
290 positive parent. Note: some backends may ignore the tree
291 structure, others may use it e.g. to group path components. We
292 assume that in the input, point 0 of each path is an "upper left"
293 corner of the path, as returned by bm_to_pathlist. This makes it
294 easy to find an "interior" point. The bm argument should be a
295 bitmap of the correct size (large enough to hold all the paths),
296 and will be used as scratch space. Return 0 on success or -1 on
297 error with errno set. */
298
299static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) {
300 path_t *p, *p1;
301 path_t *heap, *heap1;
302 path_t *cur;
303 path_t *head;
304 path_t **plist_hook; /* for fast appending to linked list */
305 path_t **hook_in, **hook_out; /* for fast appending to linked list */
306 bbox_t bbox;
307
308 bm_clear(bm, 0);
309
310 /* save original "next" pointers */
311 list_forall(p, plist) {
312 p->sibling = p->next;
313 p->childlist = NULL;
314 }
315
316 heap = plist;
317
318 /* the heap holds a list of lists of paths. Use "childlist" field
319 for outer list, "next" field for inner list. Each of the sublists
320 is to be turned into a tree. This code is messy, but it is
321 actually fast. Each path is rendered exactly once. We use the
322 heap to get a tail recursive algorithm: the heap holds a list of
323 pathlists which still need to be transformed. */
324
325 while (heap) {
326 /* unlink first sublist */
327 cur = heap;
328 heap = heap->childlist;
329 cur->childlist = NULL;
330
331 /* unlink first path */
332 head = cur;
333 cur = cur->next;
334 head->next = NULL;
335
336 /* render path */
337 xor_path(bm, head);
338 setbbox_path(&bbox, head);
339
340 /* now do insideness test for each element of cur; append it to
341 head->childlist if it's inside head, else append it to
342 head->next. */
343 hook_in=&head->childlist;
344 hook_out=&head->next;
345 list_forall_unlink(p, cur) {
346 if (p->priv->pt[0].y <= bbox.y0) {
347 list_insert_beforehook(p, hook_out);
348 /* append the remainder of the list to hook_out */
349 *hook_out = cur;
350 break;
351 }
352 if (BM_GET(bm, p->priv->pt[0].x, p->priv->pt[0].y-1)) {
353 list_insert_beforehook(p, hook_in);
354 } else {
355 list_insert_beforehook(p, hook_out);
356 }
357 }
358
359 /* clear bm */
360 clear_bm_with_bbox(bm, &bbox);
361
362 /* now schedule head->childlist and head->next for further
363 processing */
364 if (head->next) {
365 head->next->childlist = heap;
366 heap = head->next;
367 }
368 if (head->childlist) {
369 head->childlist->childlist = heap;
370 heap = head->childlist;
371 }
372 }
373
374 /* copy sibling structure from "next" to "sibling" component */
375 p = plist;
376 while (p) {
377 p1 = p->sibling;
378 p->sibling = p->next;
379 p = p1;
380 }
381
382 /* reconstruct a new linked list ("next") structure from tree
383 ("childlist", "sibling") structure. This code is slightly messy,
384 because we use a heap to make it tail recursive: the heap
385 contains a list of childlists which still need to be
386 processed. */
387 heap = plist;
388 if (heap) {
389 heap->next = NULL; /* heap is a linked list of childlists */
390 }
391 plist = NULL;
392 plist_hook = &plist;
393 while (heap) {
394 heap1 = heap->next;
395 for (p=heap; p; p=p->sibling) {
396 /* p is a positive path */
397 /* append to linked list */
398 list_insert_beforehook(p, plist_hook);
399
400 /* go through its children */
401 for (p1=p->childlist; p1; p1=p1->sibling) {
402 /* append to linked list */
403 list_insert_beforehook(p1, plist_hook);
404 /* append its childlist to heap, if non-empty */
405 if (p1->childlist) {
406 list_append(path_t, heap1, p1->childlist);
407 }
408 }
409 }
410 heap = heap1;
411 }
412
413 return;
414}
415
416/* find the next set pixel in a row <= y. Pixels are searched first
417 left-to-right, then top-down. In other words, (x,y)<(x',y') if y>y'
418 or y=y' and x<x'. If found, return 0 and store pixel in
419 (*xp,*yp). Else return 1. Note that this function assumes that
420 excess bytes have been cleared with bm_clearexcess. */
421static int findnext(potrace_bitmap_t *bm, int *xp, int *yp) {
422 int x;
423 int y;
424 int x0;
425
426 x0 = (*xp) & ~(BM_WORDBITS-1);
427
428 for (y=*yp; y>=0; y--) {
429 for (x=x0; x<bm->w; x+=BM_WORDBITS) {
430 if (*bm_index(bm, x, y)) {
431 while (!BM_GET(bm, x, y)) {
432 x++;
433 }
434 /* found */
435 *xp = x;
436 *yp = y;
437 return 0;
438 }
439 }
440 x0 = 0;
441 }
442 /* not found */
443 return 1;
444}
445
446/* Decompose the given bitmap into paths. Returns a linked list of
447 path_t objects with the fields len, pt, area, sign filled
448 in. Returns 0 on success with plistp set, or -1 on error with errno
449 set. */
450
451int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress) {
452 int x;
453 int y;
454 path_t *p;
455 path_t *plist = NULL; /* linked list of path objects */
456 path_t **plist_hook = &plist; /* used to speed up appending to linked list */
457 potrace_bitmap_t *bm1 = NULL;
458 int sign;
459
460 bm1 = bm_dup(bm);
461 if (!bm1) {
462 goto error;
463 }
464
465 /* be sure the byte padding on the right is set to 0, as the fast
466 pixel search below relies on it */
467 bm_clearexcess(bm1);
468
469 /* iterate through components */
470 x = 0;
471 y = bm1->h - 1;
472 while (findnext(bm1, &x, &y) == 0) {
473 /* calculate the sign by looking at the original */
474 sign = BM_GET(bm, x, y) ? '+' : '-';
475
476 /* calculate the path */
477 p = findpath(bm1, x, y+1, sign, param->turnpolicy);
478 if (p==NULL) {
479 goto error;
480 }
481
482 /* update buffered image */
483 xor_path(bm1, p);
484
485 /* if it's a turd, eliminate it, else append it to the list */
486 if (p->area <= param->turdsize) {
487 path_free(p);
488 } else {
489 list_insert_beforehook(p, plist_hook);
490 }
491
492 if (bm1->h > 0) { /* to be sure */
493 progress_update(1-y/(double)bm1->h, progress);
494 }
495 }
496
497 pathlist_to_tree(plist, bm1);
498 bm_free(bm1);
499 *plistp = plist;
500
501 progress_update(1.0, progress);
502
503 return 0;
504
505 error:
506 bm_free(bm1);
507 list_forall_unlink(p, plist) {
508 path_free(p);
509 }
510 return -1;
511}
5120
=== removed file 'src/trace/potrace/decompose.h'
--- src/trace/potrace/decompose.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/decompose.h 1970-01-01 00:00:00 +0000
@@ -1,16 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6#ifndef DECOMPOSE_H
7#define DECOMPOSE_H
8
9#include "potracelib.h"
10#include "progress.h"
11#include "curve.h"
12
13int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress);
14
15#endif /* DECOMPOSE_H */
16
170
=== removed file 'src/trace/potrace/greymap.cpp'
--- src/trace/potrace/greymap.cpp 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/greymap.cpp 1970-01-01 00:00:00 +0000
@@ -1,941 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6/* Routines for manipulating greymaps, including reading pgm files. We
7 only deal with greymaps of depth 8 bits. */
8
9#include <stdlib.h>
10#include <string.h>
11#include <math.h>
12#include <errno.h>
13
14#include "greymap.h"
15#include "bitops.h"
16
17#define INTBITS (8*sizeof(int))
18
19#define mod(a,n) ((a)>=(n) ? (a)%(n) : (a)>=0 ? (a) : (n)-1-(-1-(a))%(n))
20
21static int gm_readbody_pnm(FILE *f, greymap_t **gmp, int magic);
22static int gm_readbody_bmp(FILE *f, greymap_t **gmp);
23
24/* ---------------------------------------------------------------------- */
25/* basic greymap routines */
26
27/* return new un-initialized greymap. NULL with errno on error.
28 Assumes w, h >= 0. */
29greymap_t *gm_new(int w, int h) {
30 greymap_t *gm;
31 ssize_t size = (ssize_t)w * (ssize_t)h * (ssize_t)sizeof(signed short int);
32
33 /* check for overflow error */
34 if (size < 0 || size / w / h != sizeof(signed short int)) {
35 errno = ENOMEM;
36 return NULL;
37 }
38
39 gm = (greymap_t *) malloc(sizeof(greymap_t));
40 if (!gm) {
41 return NULL;
42 }
43 gm->w = w;
44 gm->h = h;
45 gm->map = (signed short int *) malloc(size);
46 if (!gm->map) {
47 free(gm);
48 return NULL;
49 }
50 return gm;
51}
52
53/* free the given greymap */
54void gm_free(greymap_t *gm) {
55 if (gm) {
56 free(gm->map);
57 }
58 free(gm);
59}
60
61/* duplicate the given greymap. Return NULL on error with errno set. */
62greymap_t *gm_dup(greymap_t *gm) {
63 greymap_t *gm1 = gm_new(gm->w, gm->h);
64 if (!gm1) {
65 return NULL;
66 }
67 memcpy(gm1->map, gm->map, gm->w*gm->h*sizeof(signed short int));
68 return gm1;
69}
70
71/* clear the given greymap to color b. */
72void gm_clear(greymap_t *gm, int b) {
73 if (b==0) {
74 memset(gm->map, 0, gm->w*gm->h*sizeof(signed short int));
75 } else {
76 for (int i=0; i<gm->w*gm->h; i++) {
77 gm->map[i] = b;
78 }
79 }
80}
81
82/* ---------------------------------------------------------------------- */
83/* routines for reading pnm streams */
84
85/* read next character after whitespace and comments. Return EOF on
86 end of file or error. */
87static int fgetc_ws(FILE *f) {
88 int c;
89
90 while (1) {
91 c = fgetc(f);
92 if (c=='#') {
93 while (1) {
94 c = fgetc(f);
95 if (c=='\n' || c==EOF) {
96 break;
97 }
98 }
99 }
100 /* space, tab, line feed, carriage return, form-feed */
101 if (c!=' ' && c!='\t' && c!='\r' && c!='\n' && c!=12) {
102 return c;
103 }
104 }
105}
106
107/* skip whitespace and comments, then read a non-negative decimal
108 number from a stream. Return -1 on EOF. Tolerate other errors (skip
109 bad characters). Do not the read any characters following the
110 number (put next character back into the stream) */
111
112static int readnum(FILE *f) {
113 int c;
114 int acc;
115
116 /* skip whitespace and comments */
117 while (1) {
118 c = fgetc_ws(f);
119 if (c==EOF) {
120 return -1;
121 }
122 if (c>='0' && c<='9') {
123 break;
124 }
125 }
126
127 /* first digit is already in c */
128 acc = c-'0';
129 while (1) {
130 c = fgetc(f);
131 if (c==EOF) {
132 break;
133 }
134 if (c<'0' || c>'9') {
135 ungetc(c, f);
136 break;
137 }
138 acc *= 10;
139 acc += c-'0';
140 }
141 return acc;
142}
143
144/* similar to readnum, but read only a single 0 or 1, and do not read
145 any characters after it. */
146
147static int readbit(FILE *f) {
148 int c;
149
150 /* skip whitespace and comments */
151 while (1) {
152 c = fgetc_ws(f);
153 if (c==EOF) {
154 return -1;
155 }
156 if (c>='0' && c<='1') {
157 break;
158 }
159 }
160
161 return c-'0';
162}
163
164/* ---------------------------------------------------------------------- */
165
166/* read a PNM stream: P1-P6 format (see pnm(5)), or a BMP stream, and
167 convert the output to a greymap. Return greymap in *gmp. Return 0
168 on success, -1 on error with errno set, -2 on bad file format (with
169 error message in gm_read_error), and 1 on premature end of file, -3
170 on empty file (including files with only whitespace and comments),
171 -4 if wrong magic number. If the return value is >=0, *gmp is
172 valid. */
173
174char const *gm_read_error = NULL;
175
176int gm_read(FILE *f, greymap_t **gmp) {
177 int magic[2];
178
179 /* read magic number. We ignore whitespace and comments before the
180 magic, for the benefit of concatenated files in P1-P3 format.
181 Multiple P1-P3 images in a single file are not formally allowed
182 by the PNM standard, but there is no harm in being lenient. */
183
184 magic[0] = fgetc_ws(f);
185 if (magic[0] == EOF) {
186 /* files which contain only comments and whitespace count as "empty" */
187 return -3;
188 }
189 magic[1] = fgetc(f);
190 if (magic[0] == 'P' && magic[1] >= '1' && magic[1] <= '6') {
191 return gm_readbody_pnm(f, gmp, magic[1]);
192 }
193 if (magic[0] == 'B' && magic[1] == 'M') {
194 return gm_readbody_bmp(f, gmp);
195 }
196 return -4;
197}
198
199/* ---------------------------------------------------------------------- */
200/* read PNM format */
201
202/* read PNM stream after magic number. Return values as for gm_read */
203static int gm_readbody_pnm(FILE *f, greymap_t **gmp, int magic) {
204 greymap_t *gm;
205 int x, y, i, j, b, b1, sum;
206 int bpr; /* bytes per row (as opposed to 4*gm->c) */
207 int w, h, max;
208
209 gm = NULL;
210
211 w = readnum(f);
212 if (w<0) {
213 goto format_error;
214 }
215
216 h = readnum(f);
217 if (h<0) {
218 goto format_error;
219 }
220
221 /* allocate greymap */
222 gm = gm_new(w, h);
223 if (!gm) {
224 return -1;
225 }
226
227 /* zero it out */
228 gm_clear(gm, 0);
229
230 switch (magic) {
231 default:
232 /* not reached */
233 goto format_error;
234
235 case '1':
236 /* read P1 format: PBM ascii */
237
238 for (y=h-1; y>=0; y--) {
239 for (x=0; x<w; x++) {
240 b = readbit(f);
241 if (b<0) {
242 goto eof;
243 }
244 GM_UPUT(gm, x, y, b ? 0 : 255);
245 }
246 }
247 break;
248
249 case '2':
250 /* read P2 format: PGM ascii */
251
252 max = readnum(f);
253 if (max<1) {
254 goto format_error;
255 }
256
257 for (y=h-1; y>=0; y--) {
258 for (x=0; x<w; x++) {
259 b = readnum(f);
260 if (b<0) {
261 goto eof;
262 }
263 GM_UPUT(gm, x, y, b*255/max);
264 }
265 }
266 break;
267
268 case '3':
269 /* read P3 format: PPM ascii */
270
271 max = readnum(f);
272 if (max<1) {
273 goto format_error;
274 }
275
276 for (y=h-1; y>=0; y--) {
277 for (x=0; x<w; x++) {
278 sum = 0;
279 for (i=0; i<3; i++) {
280 b = readnum(f);
281 if (b<0) {
282 goto eof;
283 }
284 sum += b;
285 }
286 GM_UPUT(gm, x, y, sum*(255/3)/max);
287 }
288 }
289 break;
290
291 case '4':
292 /* read P4 format: PBM raw */
293
294 b = fgetc(f); /* read single white-space character after height */
295 if (b==EOF) {
296 goto format_error;
297 }
298
299 bpr = (w+7)/8;
300
301 for (y=h-1; y>=0; y--) {
302 for (i=0; i<bpr; i++) {
303 b = fgetc(f);
304 if (b==EOF) {
305 goto eof;
306 }
307 for (j=0; j<8; j++) {
308 GM_PUT(gm, i*8+j, y, b & (0x80 >> j) ? 0 : 255);
309 }
310 }
311 }
312 break;
313
314 case '5':
315 /* read P5 format: PGM raw */
316
317 max = readnum(f);
318 if (max<1) {
319 goto format_error;
320 }
321
322 b = fgetc(f); /* read single white-space character after max */
323 if (b==EOF) {
324 goto format_error;
325 }
326
327 for (y=h-1; y>=0; y--) {
328 for (x=0; x<w; x++) {
329 b = fgetc(f);
330 if (b==EOF)
331 goto eof;
332 if (max>=256) {
333 b <<= 8;
334 b1 = fgetc(f);
335 if (b1==EOF)
336 goto eof;
337 b |= b1;
338 }
339 GM_UPUT(gm, x, y, b*255/max);
340 }
341 }
342 break;
343
344 case '6':
345 /* read P6 format: PPM raw */
346
347 max = readnum(f);
348 if (max<1) {
349 goto format_error;
350 }
351
352 b = fgetc(f); /* read single white-space character after max */
353 if (b==EOF) {
354 goto format_error;
355 }
356
357 for (y=h-1; y>=0; y--) {
358 for (x=0; x<w; x++) {
359 sum = 0;
360 for (i=0; i<3; i++) {
361 b = fgetc(f);
362 if (b==EOF) {
363 goto eof;
364 }
365 if (max>=256) {
366 b <<= 8;
367 b1 = fgetc(f);
368 if (b1==EOF)
369 goto eof;
370 b |= b1;
371 }
372 sum += b;
373 }
374 GM_UPUT(gm, x, y, sum*(255/3)/max);
375 }
376 }
377 break;
378 }
379
380 *gmp = gm;
381 return 0;
382
383 eof:
384 *gmp = gm;
385 return 1;
386
387 format_error:
388 gm_free(gm);
389 if (magic == '1' || magic == '4') {
390 gm_read_error = "invalid pbm file";
391 } else if (magic == '2' || magic == '5') {
392 gm_read_error = "invalid pgm file";
393 } else {
394 gm_read_error = "invalid ppm file";
395 }
396 return -2;
397}
398
399/* ---------------------------------------------------------------------- */
400/* read BMP format */
401
402struct bmp_info_s {
403 unsigned int FileSize;
404 unsigned int reserved;
405 unsigned int DataOffset;
406 unsigned int InfoSize;
407 unsigned int w; /* width */
408 unsigned int h; /* height */
409 unsigned int Planes;
410 unsigned int bits; /* bits per sample */
411 unsigned int comp; /* compression mode */
412 unsigned int ImageSize;
413 unsigned int XpixelsPerM;
414 unsigned int YpixelsPerM;
415 unsigned int ncolors; /* number of colors in palette */
416 unsigned int ColorsImportant;
417 unsigned int RedMask;
418 unsigned int GreenMask;
419 unsigned int BlueMask;
420 unsigned int AlphaMask;
421 unsigned int ctbits; /* sample size for color table */
422 int topdown; /* top-down mode? */
423};
424typedef struct bmp_info_s bmp_info_t;
425
426/* auxiliary */
427
428static int bmp_count = 0; /* counter for byte padding */
429static int bmp_pos = 0; /* counter from start of BMP data */
430
431/* read n-byte little-endian integer. Return 1 on EOF or error, else
432 0. Assume n<=4. */
433static int bmp_readint(FILE *f, int n, unsigned int *p) {
434 int i;
435 unsigned int sum = 0;
436 int b;
437
438 for (i=0; i<n; i++) {
439 b = fgetc(f);
440 if (b==EOF) {
441 return 1;
442 }
443 sum += b << (8*i);
444 }
445 bmp_count += n;
446 bmp_pos += n;
447 *p = sum;
448 return 0;
449}
450
451/* reset padding boundary */
452static void bmp_pad_reset(void) {
453 bmp_count = 0;
454}
455
456/* read padding bytes to 4-byte boundary. Return 1 on EOF or error,
457 else 0. */
458static int bmp_pad(FILE *f) {
459 int c, i, b;
460
461 c = (-bmp_count) & 3;
462 for (i=0; i<c; i++) {
463 b = fgetc(f);
464 if (b==EOF) {
465 return 1;
466 }
467 }
468 bmp_pos += c;
469 bmp_count = 0;
470 return 0;
471}
472
473/* forward to the new file position. Return 1 on EOF or error, else 0 */
474static int bmp_forward(FILE *f, int pos) {
475 int b;
476
477 while (bmp_pos < pos) {
478 b = fgetc(f);
479 if (b==EOF) {
480 return 1;
481 }
482 bmp_pos++;
483 bmp_count++;
484 }
485 return 0;
486}
487
488#define TRY(x) if (x) goto try_error
489#define TRY_EOF(x) if (x) goto eof
490
491/* correct y-coordinate for top-down format */
492#define ycorr(y) (bmpinfo.topdown ? bmpinfo.h-1-y : y)
493
494/* read BMP stream after magic number. Return values as for gm_read.
495 We choose to be as permissive as possible, since there are many
496 programs out there which produce BMP. For instance, ppmtobmp can
497 produce codings with anywhere from 1-8 or 24 bits per sample,
498 although most specifications only allow 1,4,8,24,32. We can also
499 read both the old and new OS/2 BMP formats in addition to the
500 Windows BMP format. */
501static int gm_readbody_bmp(FILE *f, greymap_t **gmp) {
502 bmp_info_t bmpinfo;
503 int *coltable;
504 unsigned int b, c;
505 unsigned int i, j;
506 greymap_t *gm;
507 unsigned int x, y;
508 int col[2];
509 unsigned int bitbuf;
510 unsigned int n;
511 unsigned int redshift, greenshift, blueshift;
512
513 gm_read_error = NULL;
514 gm = NULL;
515 coltable = NULL;
516
517 bmp_pos = 2; /* set file position */
518
519 /* file header (minus magic number) */
520 TRY(bmp_readint(f, 4, &bmpinfo.FileSize));
521 TRY(bmp_readint(f, 4, &bmpinfo.reserved));
522 TRY(bmp_readint(f, 4, &bmpinfo.DataOffset));
523
524 /* info header */
525 TRY(bmp_readint(f, 4, &bmpinfo.InfoSize));
526 if (bmpinfo.InfoSize == 40 || bmpinfo.InfoSize == 64
527 || bmpinfo.InfoSize == 108 || bmpinfo.InfoSize == 124) {
528 /* Windows or new OS/2 format */
529 bmpinfo.ctbits = 32; /* sample size in color table */
530 TRY(bmp_readint(f, 4, &bmpinfo.w));
531 TRY(bmp_readint(f, 4, &bmpinfo.h));
532 TRY(bmp_readint(f, 2, &bmpinfo.Planes));
533 TRY(bmp_readint(f, 2, &bmpinfo.bits));
534 TRY(bmp_readint(f, 4, &bmpinfo.comp));
535 TRY(bmp_readint(f, 4, &bmpinfo.ImageSize));
536 TRY(bmp_readint(f, 4, &bmpinfo.XpixelsPerM));
537 TRY(bmp_readint(f, 4, &bmpinfo.YpixelsPerM));
538 TRY(bmp_readint(f, 4, &bmpinfo.ncolors));
539 TRY(bmp_readint(f, 4, &bmpinfo.ColorsImportant));
540 if (bmpinfo.InfoSize >= 108) { /* V4 and V5 bitmaps */
541 TRY(bmp_readint(f, 4, &bmpinfo.RedMask));
542 TRY(bmp_readint(f, 4, &bmpinfo.GreenMask));
543 TRY(bmp_readint(f, 4, &bmpinfo.BlueMask));
544 TRY(bmp_readint(f, 4, &bmpinfo.AlphaMask));
545 }
546 if (bmpinfo.w > 0x7fffffff) {
547 goto format_error;
548 }
549 if (bmpinfo.h > 0x7fffffff) {
550 bmpinfo.h = (-bmpinfo.h) & 0xffffffff;
551 bmpinfo.topdown = 1;
552 } else {
553 bmpinfo.topdown = 0;
554 }
555 if (bmpinfo.h > 0x7fffffff) {
556 goto format_error;
557 }
558 } else if (bmpinfo.InfoSize == 12) {
559 /* old OS/2 format */
560 bmpinfo.ctbits = 24; /* sample size in color table */
561 TRY(bmp_readint(f, 2, &bmpinfo.w));
562 TRY(bmp_readint(f, 2, &bmpinfo.h));
563 TRY(bmp_readint(f, 2, &bmpinfo.Planes));
564 TRY(bmp_readint(f, 2, &bmpinfo.bits));
565 bmpinfo.comp = 0;
566 bmpinfo.ncolors = 0;
567 bmpinfo.topdown = 0;
568 } else {
569 goto format_error;
570 }
571
572 if (bmpinfo.comp == 3 && bmpinfo.InfoSize < 108) {
573 /* bitfield feature is only understood with V4 and V5 format */
574 goto format_error;
575 }
576
577 /* forward to color table (e.g., if bmpinfo.InfoSize == 64) */
578 TRY(bmp_forward(f, 14+bmpinfo.InfoSize));
579
580 if (bmpinfo.Planes != 1) {
581 gm_read_error = "cannot handle bmp planes";
582 goto format_error; /* can't handle planes */
583 }
584
585 if (bmpinfo.ncolors == 0) {
586 bmpinfo.ncolors = 1 << bmpinfo.bits;
587 }
588
589 /* color table, present only if bmpinfo.bits <= 8. */
590 if (bmpinfo.bits <= 8) {
591 coltable = (int *) calloc(bmpinfo.ncolors, sizeof(int));
592 if (!coltable) {
593 goto std_error;
594 }
595 /* NOTE: since we are reading a greymap, we can immediately convert
596 the color table entries to grey values. */
597 for (i=0; i<bmpinfo.ncolors; i++) {
598 TRY(bmp_readint(f, bmpinfo.ctbits/8, &c));
599 c = ((c>>16) & 0xff) + ((c>>8) & 0xff) + (c & 0xff);
600 coltable[i] = c/3;
601 }
602 }
603
604 /* forward to data */
605 if (bmpinfo.InfoSize != 12) { /* not old OS/2 format */
606 TRY(bmp_forward(f, bmpinfo.DataOffset));
607 }
608
609 /* allocate greymap */
610 gm = gm_new(bmpinfo.w, bmpinfo.h);
611 if (!gm) {
612 goto std_error;
613 }
614
615 /* zero it out */
616 gm_clear(gm, 0);
617
618 switch (bmpinfo.bits + 0x100*bmpinfo.comp) {
619
620 default:
621 goto format_error;
622 break;
623
624 case 0x001: /* monochrome palette */
625
626 /* raster data */
627 for (y=0; y<bmpinfo.h; y++) {
628 bmp_pad_reset();
629 for (i=0; 8*i<bmpinfo.w; i++) {
630 TRY_EOF(bmp_readint(f, 1, &b));
631 for (j=0; j<8; j++) {
632 GM_PUT(gm, i*8+j, ycorr(y), b & (0x80 >> j) ? coltable[1] : coltable[0]);
633 }
634 }
635 TRY(bmp_pad(f));
636 }
637 break;
638
639 case 0x002: /* 2-bit to 8-bit palettes */
640 case 0x003:
641 case 0x004:
642 case 0x005:
643 case 0x006:
644 case 0x007:
645 case 0x008:
646 for (y=0; y<bmpinfo.h; y++) {
647 bmp_pad_reset();
648 bitbuf = 0; /* bit buffer: bits in buffer are high-aligned */
649 n = 0; /* number of bits currently in bitbuffer */
650 for (x=0; x<bmpinfo.w; x++) {
651 if (n < bmpinfo.bits) {
652 TRY_EOF(bmp_readint(f, 1, &b));
653 bitbuf |= b << (INTBITS - 8 - n);
654 n += 8;
655 }
656 b = bitbuf >> (INTBITS - bmpinfo.bits);
657 bitbuf <<= bmpinfo.bits;
658 n -= bmpinfo.bits;
659 GM_UPUT(gm, x, ycorr(y), coltable[b]);
660 }
661 TRY(bmp_pad(f));
662 }
663 break;
664
665 case 0x010: /* 16-bit encoding */
666 /* can't do this format because it is not well-documented and I
667 don't have any samples */
668 gm_read_error = "cannot handle bmp 16-bit coding";
669 goto format_error;
670 break;
671
672 case 0x018: /* 24-bit encoding */
673 case 0x020: /* 32-bit encoding */
674 for (y=0; y<bmpinfo.h; y++) {
675 bmp_pad_reset();
676 for (x=0; x<bmpinfo.w; x++) {
677 TRY_EOF(bmp_readint(f, bmpinfo.bits/8, &c));
678 c = ((c>>16) & 0xff) + ((c>>8) & 0xff) + (c & 0xff);
679 GM_UPUT(gm, x, ycorr(y), c/3);
680 }
681 TRY(bmp_pad(f));
682 }
683 break;
684
685 case 0x320: /* 32-bit encoding with bitfields */
686 redshift = lobit(bmpinfo.RedMask);
687 greenshift = lobit(bmpinfo.GreenMask);
688 blueshift = lobit(bmpinfo.BlueMask);
689
690 for (y=0; y<bmpinfo.h; y++) {
691 bmp_pad_reset();
692 for (x=0; x<bmpinfo.w; x++) {
693 TRY_EOF(bmp_readint(f, bmpinfo.bits/8, &c));
694 c = ((c & bmpinfo.RedMask) >> redshift) + ((c & bmpinfo.GreenMask) >> greenshift) + ((c & bmpinfo.BlueMask) >> blueshift);
695 GM_UPUT(gm, x, ycorr(y), c/3);
696 }
697 TRY(bmp_pad(f));
698 }
699 break;
700
701 case 0x204: /* 4-bit runlength compressed encoding (RLE4) */
702 x = 0;
703 y = 0;
704 while (1) {
705 TRY_EOF(bmp_readint(f, 1, &b)); /* opcode */
706 TRY_EOF(bmp_readint(f, 1, &c)); /* argument */
707 if (b>0) {
708 /* repeat count */
709 col[0] = coltable[(c>>4) & 0xf];
710 col[1] = coltable[c & 0xf];
711 for (i=0; i<b && x<bmpinfo.w; i++) {
712 if (x>=bmpinfo.w) {
713 x=0;
714 y++;
715 }
716 if (y>=bmpinfo.h) {
717 break;
718 }
719 GM_UPUT(gm, x, ycorr(y), col[i&1]);
720 x++;
721 }
722 } else if (c == 0) {
723 /* end of line */
724 y++;
725 x = 0;
726 } else if (c == 1) {
727 /* end of greymap */
728 break;
729 } else if (c == 2) {
730 /* "delta": skip pixels in x and y directions */
731 TRY_EOF(bmp_readint(f, 1, &b)); /* x offset */
732 TRY_EOF(bmp_readint(f, 1, &c)); /* y offset */
733 x += b;
734 y += c;
735 } else {
736 /* verbatim segment */
737 for (i=0; i<c; i++) {
738 if ((i&1)==0) {
739 TRY_EOF(bmp_readint(f, 1, &b));
740 }
741 if (x>=bmpinfo.w) {
742 x=0;
743 y++;
744 }
745 if (y>=bmpinfo.h) {
746 break;
747 }
748 GM_PUT(gm, x, ycorr(y), coltable[(b>>(4-4*(i&1))) & 0xf]);
749 x++;
750 }
751 if ((c+1) & 2) {
752 /* pad to 16-bit boundary */
753 TRY_EOF(bmp_readint(f, 1, &b));
754 }
755 }
756 }
757 break;
758
759 case 0x108: /* 8-bit runlength compressed encoding (RLE8) */
760 x = 0;
761 y = 0;
762 while (1) {
763 TRY_EOF(bmp_readint(f, 1, &b)); /* opcode */
764 TRY_EOF(bmp_readint(f, 1, &c)); /* argument */
765 if (b>0) {
766 /* repeat count */
767 for (i=0; i<b; i++) {
768 if (x>=bmpinfo.w) {
769 x=0;
770 y++;
771 }
772 if (y>=bmpinfo.h) {
773 break;
774 }
775 GM_UPUT(gm, x, ycorr(y), coltable[c]);
776 x++;
777 }
778 } else if (c == 0) {
779 /* end of line */
780 y++;
781 x = 0;
782 } else if (c == 1) {
783 /* end of greymap */
784 break;
785 } else if (c == 2) {
786 /* "delta": skip pixels in x and y directions */
787 TRY_EOF(bmp_readint(f, 1, &b)); /* x offset */
788 TRY_EOF(bmp_readint(f, 1, &c)); /* y offset */
789 x += b;
790 y += c;
791 } else {
792 /* verbatim segment */
793 for (i=0; i<c; i++) {
794 TRY_EOF(bmp_readint(f, 1, &b));
795 if (x>=bmpinfo.w) {
796 x=0;
797 y++;
798 }
799 if (y>=bmpinfo.h) {
800 break;
801 }
802 GM_PUT(gm, x, ycorr(y), coltable[b]);
803 x++;
804 }
805 if (c & 1) {
806 /* pad input to 16-bit boundary */
807 TRY_EOF(bmp_readint(f, 1, &b));
808 }
809 }
810 }
811 break;
812
813 } /* switch */
814
815 /* skip any potential junk after the data section, but don't
816 complain in case EOF is encountered */
817 bmp_forward(f, bmpinfo.FileSize);
818
819 free(coltable);
820 *gmp = gm;
821 return 0;
822
823 eof:
824 free(coltable);
825 *gmp = gm;
826 return 1;
827
828 format_error:
829 try_error:
830 free(coltable);
831 free(gm);
832 if (!gm_read_error) {
833 gm_read_error = "invalid bmp file";
834 }
835 return -2;
836
837 std_error:
838 free(coltable);
839 free(gm);
840 return -1;
841}
842
843/* ---------------------------------------------------------------------- */
844
845/* write a pgm stream, either P2 or (if raw != 0) P5 format. Include
846 one-line comment if non-NULL. Mode determines how out-of-range
847 color values are converted. Gamma is the desired gamma correction,
848 if any (set to 2.2 if the image is to look optimal on a CRT monitor,
849 2.8 for LCD). Set to 1.0 for no gamma correction */
850
851int gm_writepgm(FILE *f, greymap_t *gm, char *comment, int raw, int mode, double gamma) {
852 int x, y, v;
853 int gammatable[256];
854
855 /* prepare gamma correction lookup table */
856 if (gamma != 1.0) {
857 gammatable[0] = 0;
858 for (v=1; v<256; v++) {
859 gammatable[v] = (int)(255 * exp(log(v/255.0)/gamma) + 0.5);
860 }
861 } else {
862 for (v=0; v<256; v++) {
863 gammatable[v] = v;
864 }
865 }
866
867 fprintf(f, raw ? "P5\n" : "P2\n");
868 if (comment && *comment) {
869 fprintf(f, "# %s\n", comment);
870 }
871 fprintf(f, "%d %d 255\n", gm->w, gm->h);
872 for (y=gm->h-1; y>=0; y--) {
873 for (x=0; x<gm->w; x++) {
874 v = GM_UGET(gm, x, y);
875 if (mode == GM_MODE_NONZERO) {
876 if (v > 255) {
877 v = 510 - v;
878 }
879 if (v < 0) {
880 v = 0;
881 }
882 } else if (mode == GM_MODE_ODD) {
883 v = mod(v, 510);
884 if (v > 255) {
885 v = 510 - v;
886 }
887 } else if (mode == GM_MODE_POSITIVE) {
888 if (v < 0) {
889 v = 0;
890 } else if (v > 255) {
891 v = 255;
892 }
893 } else if (mode == GM_MODE_NEGATIVE) {
894 v = 510 - v;
895 if (v < 0) {
896 v = 0;
897 } else if (v > 255) {
898 v = 255;
899 }
900 }
901 v = gammatable[v];
902
903 if (raw) {
904 fputc(v, f);
905 } else {
906 fprintf(f, x == gm->w-1 ? "%d\n" : "%d ", v);
907 }
908 }
909 }
910 return 0;
911}
912
913/* ---------------------------------------------------------------------- */
914/* output - for primitive debugging purposes only! */
915
916/* print greymap to screen */
917int gm_print(FILE *f, greymap_t *gm) {
918 int x, y;
919 int xx, yy;
920 int d, t;
921 int sw, sh;
922
923 sw = gm->w < 79 ? gm->w : 79;
924 sh = gm->w < 79 ? gm->h : gm->h*sw*44/(79*gm->w);
925
926 for (yy=sh-1; yy>=0; yy--) {
927 for (xx=0; xx<sw; xx++) {
928 d=0;
929 t=0;
930 for (x=xx*gm->w/sw; x<(xx+1)*gm->w/sw; x++) {
931 for (y=yy*gm->h/sh; y<(yy+1)*gm->h/sh; y++) {
932 d += GM_GET(gm, x, y);
933 t += 256;
934 }
935 }
936 fputc("*#=- "[5*d/t], f); /* what a cute trick :) */
937 }
938 fputc('\n', f);
939 }
940 return 0;
941}
9420
=== removed file 'src/trace/potrace/greymap.h'
--- src/trace/potrace/greymap.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/greymap.h 1970-01-01 00:00:00 +0000
@@ -1,58 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6#ifndef GREYMAP_H
7#define GREYMAP_H
8
9#include <stdio.h>
10#include <stdlib.h>
11
12/* internal format for greymaps. Note: in this format, rows are
13 ordered from bottom to top. The pixels in each row are given from
14 left to right. */
15
16struct greymap_s {
17 int w; /* width, in pixels */
18 int h; /* height, in pixels */
19 signed short int *map; /* raw data, w*h values */
20};
21typedef struct greymap_s greymap_t;
22
23/* macros for accessing pixel at index (x,y). Note that the origin is
24 in the *lower* left corner. U* macros omit the bounds check. */
25
26#define gm_index(gm, x, y) (&(gm)->map[(x)+(y)*(ssize_t)(gm)->w])
27#define gm_safe(gm, x, y) ((int)(x)>=0 && (int)(x)<(gm)->w && (int)(y)>=0 && (int)(y)<(gm)->h)
28#define gm_bound(x, m) ((x)<0 ? 0 : (x)>=(m) ? (m)-1 : (x))
29#define GM_UGET(gm, x, y) (*gm_index(gm, x, y))
30#define GM_UINC(gm, x, y, b) (*gm_index(gm, x, y) += (short int)(b))
31#define GM_UINV(gm, x, y) (*gm_index(gm, x, y) = 255 - *gm_index(gm, x, y))
32#define GM_UPUT(gm, x, y, b) (*gm_index(gm, x, y) = (short int)(b))
33#define GM_GET(gm, x, y) (gm_safe(gm, x, y) ? GM_UGET(gm, x, y) : 0)
34#define GM_INC(gm, x, y, b) (gm_safe(gm, x, y) ? GM_UINC(gm, x, y, b) : 0)
35#define GM_INV(gm, x, y) (gm_safe(gm, x, y) ? GM_UINV(gm, x, y) : 0)
36#define GM_PUT(gm, x, y, b) (gm_safe(gm, x, y) ? GM_UPUT(gm, x, y, b) : 0)
37#define GM_BGET(gm, x, y) GM_UGET(gm, gm_bound(x, gm->w), gm_bound(y, gm->h))
38
39/* modes for cutting off out-of-range values. The following names
40 refer to winding numbers. I.e., make a pixel black if winding
41 number is nonzero, odd, or positive, respectively. We assume that 0
42 winding number corresponds to white (255). */
43#define GM_MODE_NONZERO 1
44#define GM_MODE_ODD 2
45#define GM_MODE_POSITIVE 3
46#define GM_MODE_NEGATIVE 4
47
48extern char const *gm_read_error;
49
50greymap_t *gm_new(int w, int h);
51greymap_t *gm_dup(greymap_t *gm);
52void gm_free(greymap_t *gm);
53void gm_clear(greymap_t *gm, int b);
54int gm_read(FILE *f, greymap_t **gmp);
55int gm_writepgm(FILE *f, greymap_t *gm, char *comment, int raw, int mode, double gamma);
56int gm_print(FILE *f, greymap_t *gm);
57
58#endif /* GREYMAP_H */
590
=== modified file 'src/trace/potrace/inkscape-potrace.cpp'
--- src/trace/potrace/inkscape-potrace.cpp 2015-06-22 19:16:52 +0000
+++ src/trace/potrace/inkscape-potrace.cpp 2015-11-21 12:39:21 +0000
@@ -29,7 +29,6 @@
29#include "message-stack.h"29#include "message-stack.h"
30#include <sp-path.h>30#include <sp-path.h>
31#include <svg/path-string.h>31#include <svg/path-string.h>
32#include "curve.h"
33#include "bitmap.h"32#include "bitmap.h"
3433
35using Glib::ustring;34using Glib::ustring;
@@ -128,7 +127,7 @@
128127
129128
130/**129/**
131 * Recursively descend the path_t node tree, writing paths in SVG130 * Recursively descend the potrace_path_t node tree, writing paths in SVG
132 * format into the output stream. The Point vector is used to prevent131 * format into the output stream. The Point vector is used to prevent
133 * redundant paths. Returns number of paths processed.132 * redundant paths. Returns number of paths processed.
134 */133 */
@@ -144,7 +143,7 @@
144 //g_message("node->fm:%d\n", node->fm);143 //g_message("node->fm:%d\n", node->fm);
145 if (!curve->n)144 if (!curve->n)
146 continue;145 continue;
147 dpoint_t *pt = curve->c[curve->n - 1];146 const potrace_dpoint_t *pt = curve->c[curve->n - 1];
148 double x0 = 0.0;147 double x0 = 0.0;
149 double y0 = 0.0;148 double y0 = 0.0;
150 double x1 = 0.0;149 double x1 = 0.0;
@@ -192,7 +191,7 @@
192 }191 }
193 data.closePath();192 data.closePath();
194193
195 for (path_t *child=node->childlist; child ; child=child->sibling)194 for (potrace_path_t *child=node->childlist; child ; child=child->sibling)
196 {195 {
197 nodeCount += writePaths(engine, child, data, points);196 nodeCount += writePaths(engine, child, data, points);
198 }197 }
199198
=== modified file 'src/trace/potrace/inkscape-potrace.h'
--- src/trace/potrace/inkscape-potrace.h 2012-02-29 01:16:51 +0000
+++ src/trace/potrace/inkscape-potrace.h 2015-11-21 12:39:21 +0000
@@ -18,7 +18,7 @@
18#define __INKSCAPE_POTRACE_H__18#define __INKSCAPE_POTRACE_H__
1919
20#include <trace/trace.h>20#include <trace/trace.h>
21#include "potracelib.h"21#include <potracelib.h>
2222
23struct GrayMap_def;23struct GrayMap_def;
24typedef GrayMap_def GrayMap;24typedef GrayMap_def GrayMap;
2525
=== removed file 'src/trace/potrace/lists.h'
--- src/trace/potrace/lists.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/lists.h 1970-01-01 00:00:00 +0000
@@ -1,285 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6#ifndef _PS_LISTS_H
7#define _PS_LISTS_H
8
9/* here we define some general list macros. Because they are macros,
10 they should work on any datatype with a "->next" component. Some of
11 them use a "hook". If elt and list are of type t* then hook is of
12 type t**. A hook stands for an insertion point in the list, i.e.,
13 either before the first element, or between two elements, or after
14 the last element. If an operation "sets the hook" for an element,
15 then the hook is set to just before the element. One can insert
16 something at a hook. One can also unlink at a hook: this means,
17 unlink the element just after the hook. By "to unlink", we mean the
18 element is removed from the list, but not deleted. Thus, it and its
19 components still need to be freed. */
20
21/* Note: these macros are somewhat experimental. Only the ones that
22 are actually *used* have been tested. So be careful to test any
23 that you use. Looking at the output of the preprocessor, "gcc -E"
24 (possibly piped though "indent"), might help too. Also: these
25 macros define some internal (local) variables that start with
26 "_". */
27
28/* we enclose macro definitions whose body consists of more than one
29 statement in MACRO_BEGIN and MACRO_END, rather than '{' and '}'. The
30 reason is that we want to be able to use the macro in a context
31 such as "if (...) macro(...); else ...". If we didn't use this obscure
32 trick, we'd have to omit the ";" in such cases. */
33
34#define MACRO_BEGIN do {
35#define MACRO_END } while (0)
36
37/* ---------------------------------------------------------------------- */
38/* macros for singly-linked lists */
39
40/* traverse list. At the end, elt is set to NULL. */
41#define list_forall(elt, list) for (elt=list; elt!=NULL; elt=elt->next)
42
43/* set elt to the first element of list satisfying boolean condition
44 c, or NULL if not found */
45#define list_find(elt, list, c) \
46 MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END
47
48/* like forall, except also set hook for elt. */
49#define list_forall2(elt, list, hook) \
50 for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next)
51
52/* same as list_find, except also set hook for elt. */
53#define list_find2(elt, list, c, hook) \
54 MACRO_BEGIN list_forall2(elt, list, hook) if (c) break; MACRO_END
55
56/* same, except only use hook. */
57#define _list_forall_hook(list, hook) \
58 for (hook=&list; *hook!=NULL; hook=&(*hook)->next)
59
60/* same, except only use hook. Note: c may only refer to *hook, not elt. */
61#define _list_find_hook(list, c, hook) \
62 MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END
63
64/* insert element after hook */
65#define list_insert_athook(elt, hook) \
66 MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
67
68/* insert element before hook */
69#define list_insert_beforehook(elt, hook) \
70 MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END
71
72/* unlink element after hook, let elt be unlinked element, or NULL.
73 hook remains. */
74#define list_unlink_athook(list, elt, hook) \
75 MACRO_BEGIN \
76 elt = hook ? *hook : NULL; if (elt) { *hook = elt->next; elt->next = NULL; }\
77 MACRO_END
78
79/* unlink the specific element, if it is in the list. Otherwise, set
80 elt to NULL */
81#define list_unlink(listtype, list, elt) \
82 MACRO_BEGIN \
83 listtype **_hook; \
84 _list_find_hook(list, *_hook==elt, _hook); \
85 list_unlink_athook(list, elt, _hook); \
86 MACRO_END
87
88/* prepend elt to list */
89#define list_prepend(list, elt) \
90 MACRO_BEGIN elt->next = list; list = elt; MACRO_END
91
92/* append elt to list. */
93#define list_append(listtype, list, elt) \
94 MACRO_BEGIN \
95 listtype **_hook; \
96 _list_forall_hook(list, _hook) {} \
97 list_insert_athook(elt, _hook); \
98 MACRO_END
99
100/* unlink the first element that satisfies the condition. */
101#define list_unlink_cond(listtype, list, elt, c) \
102 MACRO_BEGIN \
103 listtype **_hook; \
104 list_find2(elt, list, c, _hook); \
105 list_unlink_athook(list, elt, _hook); \
106 MACRO_END
107
108/* let elt be the nth element of the list, starting to count from 0.
109 Return NULL if out of bounds. */
110#define list_nth(elt, list, n) \
111 MACRO_BEGIN \
112 int _x; /* only evaluate n once */ \
113 for (_x=(n), elt=list; _x && elt; _x--, elt=elt->next) {} \
114 MACRO_END
115
116/* let elt be the nth element of the list, starting to count from 0.
117 Return NULL if out of bounds. */
118#define list_nth_hook(elt, list, n, hook) \
119 MACRO_BEGIN \
120 int _x; /* only evaluate n once */ \
121 for (_x=(n), elt=list, hook=&list; _x && elt; _x--, hook=&elt->next, elt=elt->next) {} \
122 MACRO_END
123
124/* set n to the length of the list */
125#define list_length(listtype, list, n) \
126 MACRO_BEGIN \
127 listtype *_elt; \
128 n=0; \
129 list_forall(_elt, list) \
130 n++; \
131 MACRO_END
132
133/* set n to the index of the first element satisfying cond, or -1 if
134 none found. Also set elt to the element, or NULL if none found. */
135#define list_index(list, n, elt, c) \
136 MACRO_BEGIN \
137 n=0; \
138 list_forall(elt, list) { \
139 if (c) break; \
140 n++; \
141 } \
142 if (!elt) \
143 n=-1; \
144 MACRO_END
145
146/* set n to the number of elements in the list that satisfy condition c */
147#define list_count(list, n, elt, c) \
148 MACRO_BEGIN \
149 n=0; \
150 list_forall(elt, list) { \
151 if (c) n++; \
152 } \
153 MACRO_END
154
155/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
156#define list_forall_unlink(elt, list) \
157 for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list)
158
159/* reverse a list (efficient) */
160#define list_reverse(listtype, list) \
161 MACRO_BEGIN \
162 listtype *_list1=NULL, *elt; \
163 list_forall_unlink(elt, list) \
164 list_prepend(_list1, elt); \
165 list = _list1; \
166 MACRO_END
167
168/* insert the element ELT just before the first element TMP of the
169 list for which COND holds. Here COND must be a condition of ELT and
170 TMP. Typical usage is to insert an element into an ordered list:
171 for instance, list_insert_ordered(listtype, list, elt, tmp,
172 elt->size <= tmp->size). Note: if we give a "less than or equal"
173 condition, the new element will be inserted just before a sequence
174 of equal elements. If we give a "less than" condition, the new
175 element will be inserted just after a list of equal elements.
176 Note: it is much more efficient to construct a list with
177 list_prepend and then order it with list_merge_sort, than to
178 construct it with list_insert_ordered. */
179#define list_insert_ordered(listtype, list, elt, tmp, cond) \
180 MACRO_BEGIN \
181 listtype **_hook; \
182 _list_find_hook(list, (tmp=*_hook, (cond)), _hook); \
183 list_insert_athook(elt, _hook); \
184 MACRO_END
185
186/* sort the given list, according to the comparison condition.
187 Typical usage is list_sort(listtype, list, a, b, a->size <
188 b->size). Note: if we give "less than or equal" condition, each
189 segment of equal elements will be reversed in order. If we give a
190 "less than" condition, each segment of equal elements will retain
191 the original order. The latter is slower but sometimes
192 prettier. Average running time: n*n/2. */
193#define list_sort(listtype, list, a, b, cond) \
194 MACRO_BEGIN \
195 listtype *_newlist=NULL; \
196 list_forall_unlink(a, list) \
197 list_insert_ordered(listtype, _newlist, a, b, cond); \
198 list = _newlist; \
199 MACRO_END
200
201/* a much faster sort algorithm (merge sort, n log n worst case). It
202 is required that the list type has an additional, unused next1
203 component. Note there is no curious reversal of order of equal
204 elements as for list_sort. */
205
206#define list_mergesort(listtype, list, a, b, cond) \
207 MACRO_BEGIN \
208 listtype *_elt, **_hook1; \
209 \
210 for (_elt=list; _elt; _elt=_elt->next1) { \
211 _elt->next1 = _elt->next; \
212 _elt->next = NULL; \
213 } \
214 do { \
215 _hook1 = &(list); \
216 while ((a = *_hook1) != NULL && (b = a->next1) != NULL ) { \
217 _elt = b->next1; \
218 _list_merge_cond(listtype, a, b, cond, *_hook1); \
219 _hook1 = &((*_hook1)->next1); \
220 *_hook1 = _elt; \
221 } \
222 } while (_hook1 != &(list)); \
223 MACRO_END
224
225/* merge two sorted lists. Store result at &result */
226#define _list_merge_cond(listtype, a, b, cond, result) \
227 MACRO_BEGIN \
228 listtype **_hook; \
229 _hook = &(result); \
230 while (1) { \
231 if (a==NULL) { \
232 *_hook = b; \
233 break; \
234 } else if (b==NULL) { \
235 *_hook = a; \
236 break; \
237 } else if (cond) { \
238 *_hook = a; \
239 _hook = &(a->next); \
240 a = a->next; \
241 } else { \
242 *_hook = b; \
243 _hook = &(b->next); \
244 b = b->next; \
245 } \
246 } \
247 MACRO_END
248
249/* ---------------------------------------------------------------------- */
250/* macros for doubly-linked lists */
251
252#define dlist_append(head, end, elt) \
253 MACRO_BEGIN \
254 elt->prev = end; \
255 elt->next = NULL; \
256 if (end) { \
257 end->next = elt; \
258 } else { \
259 head = elt; \
260 } \
261 end = elt; \
262 MACRO_END
263
264/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
265#define dlist_forall_unlink(elt, head, end) \
266 for (elt=head; elt ? (head=elt->next, elt->next=NULL, elt->prev=NULL), 1 : (end=NULL, 0); elt=head)
267
268/* unlink the first element of the list */
269#define dlist_unlink_first(head, end, elt) \
270 MACRO_BEGIN \
271 elt = head; \
272 if (head) { \
273 head = head->next; \
274 if (head) { \
275 head->prev = NULL; \
276 } else { \
277 end = NULL; \
278 } \
279 elt->prev = NULL; \
280 elt->next = NULL; \
281 } \
282 MACRO_END
283
284#endif /* _PS_LISTS_H */
285
2860
=== removed file 'src/trace/potrace/potracelib.cpp'
--- src/trace/potrace/potracelib.cpp 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/potracelib.cpp 1970-01-01 00:00:00 +0000
@@ -1,128 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5#include <stdlib.h>
6#include <string.h>
7#include <glib.h>
8
9#include "potracelib.h"
10#include "inkscape-version.h"
11#include "curve.h"
12#include "decompose.h"
13#include "trace.h"
14#include "progress.h"
15
16#ifdef HAVE_CONFIG_H
17#include "config.h"
18#endif
19
20/* default parameters */
21static const potrace_param_t param_default = {
22 2, /* turdsize */
23 POTRACE_TURNPOLICY_MINORITY, /* turnpolicy */
24 1.0, /* alphamax */
25 1, /* opticurve */
26 0.2, /* opttolerance */
27 {
28 NULL, /* callback function */
29 NULL, /* callback data */
30 0.0, 1.0, /* progress range */
31 0.0, /* granularity */
32 },
33};
34
35/* Return a fresh copy of the set of default parameters, or NULL on
36 failure with errno set. */
37potrace_param_t *potrace_param_default(void) {
38 potrace_param_t *p;
39
40 p = (potrace_param_t *) malloc(sizeof(potrace_param_t));
41 if (!p) {
42 return NULL;
43 }
44 memcpy(p, &param_default, sizeof(potrace_param_t));
45 return p;
46}
47
48/* On success, returns a Potrace state st with st->status ==
49 POTRACE_STATUS_OK. On failure, returns NULL if no Potrace state
50 could be created (with errno set), or returns an incomplete Potrace
51 state (with st->status == POTRACE_STATUS_INCOMPLETE, and with errno
52 set). Complete or incomplete Potrace state can be freed with
53 potrace_state_free(). */
54potrace_state_t *potrace_trace(const potrace_param_t *param, const potrace_bitmap_t *bm) {
55 int r;
56 path_t *plist = NULL;
57 potrace_state_t *st;
58 progress_t prog;
59 progress_t subprog;
60
61 /* prepare private progress bar state */
62 prog.callback = param->progress.callback;
63 prog.data = param->progress.data;
64 prog.min = param->progress.min;
65 prog.max = param->progress.max;
66 prog.epsilon = param->progress.epsilon;
67 prog.d_prev = param->progress.min;
68
69 /* allocate state object */
70 st = (potrace_state_t *)malloc(sizeof(potrace_state_t));
71 if (!st) {
72 return NULL;
73 }
74
75 progress_subrange_start(0.0, 0.1, &prog, &subprog);
76
77 /* process the image */
78 r = bm_to_pathlist(bm, &plist, param, &subprog);
79 if (r) {
80 free(st);
81 return NULL;
82 }
83
84 st->status = POTRACE_STATUS_OK;
85 st->plist = plist;
86 st->priv = NULL; /* private state currently unused */
87
88 progress_subrange_end(&prog, &subprog);
89
90 progress_subrange_start(0.1, 1.0, &prog, &subprog);
91
92 /* partial success. */
93 r = process_path(plist, param, &subprog);
94 if (r) {
95 st->status = POTRACE_STATUS_INCOMPLETE;
96 }
97
98 progress_subrange_end(&prog, &subprog);
99
100 return st;
101}
102
103/* free a Potrace state, without disturbing errno. */
104void potrace_state_free(potrace_state_t *st) {
105 pathlist_free(st->plist);
106 free(st);
107}
108
109/* free a parameter list, without disturbing errno. */
110void potrace_param_free(potrace_param_t *p) {
111 free(p);
112}
113
114char *potrace_version(void) {
115 static char *ver = g_strdup_printf("potracelib %s", Inkscape::version_string);
116 return ver;
117}
118
119/*
120 Local Variables:
121 mode:c++
122 c-file-style:"stroustrup"
123 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
124 indent-tabs-mode:nil
125 fill-column:99
126 End:
127*/
128// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
1290
=== removed file 'src/trace/potrace/potracelib.h'
--- src/trace/potrace/potracelib.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/potracelib.h 1970-01-01 00:00:00 +0000
@@ -1,139 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5#ifndef POTRACELIB_H
6#define POTRACELIB_H
7
8/* this file defines the API for the core Potrace library. For a more
9 detailed description of the API, see potracelib.pdf */
10
11#ifdef __cplusplus
12extern "C" {
13#endif
14
15/* ---------------------------------------------------------------------- */
16/* tracing parameters */
17
18/* turn policies */
19#define POTRACE_TURNPOLICY_BLACK 0
20#define POTRACE_TURNPOLICY_WHITE 1
21#define POTRACE_TURNPOLICY_LEFT 2
22#define POTRACE_TURNPOLICY_RIGHT 3
23#define POTRACE_TURNPOLICY_MINORITY 4
24#define POTRACE_TURNPOLICY_MAJORITY 5
25#define POTRACE_TURNPOLICY_RANDOM 6
26
27/* structure to hold progress bar callback data */
28struct potrace_progress_s {
29 void (*callback)(double progress, void *privdata); /* callback fn */
30 void *data; /* callback function's private data */
31 double min, max; /* desired range of progress, e.g. 0.0 to 1.0 */
32 double epsilon; /* granularity: can skip smaller increments */
33};
34typedef struct potrace_progress_s potrace_progress_t;
35
36/* structure to hold tracing parameters */
37struct potrace_param_s {
38 int turdsize; /* area of largest path to be ignored */
39 int turnpolicy; /* resolves ambiguous turns in path decomposition */
40 double alphamax; /* corner threshold */
41 int opticurve; /* use curve optimization? */
42 double opttolerance; /* curve optimization tolerance */
43 potrace_progress_t progress; /* progress callback function */
44};
45typedef struct potrace_param_s potrace_param_t;
46
47/* ---------------------------------------------------------------------- */
48/* bitmaps */
49
50/* native word size */
51typedef unsigned long potrace_word;
52
53/* Internal bitmap format. The n-th scanline starts at scanline(n) =
54 (map + n*dy). Raster data is stored as a sequence of potrace_words
55 (NOT bytes). The leftmost bit of scanline n is the most significant
56 bit of scanline(n)[0]. */
57struct potrace_bitmap_s {
58 int w, h; /* width and height, in pixels */
59 int dy; /* words per scanline (not bytes) */
60 potrace_word *map; /* raw data, dy*h words */
61};
62typedef struct potrace_bitmap_s potrace_bitmap_t;
63
64/* ---------------------------------------------------------------------- */
65/* curves */
66
67/* point */
68struct potrace_dpoint_s {
69 double x, y;
70};
71typedef struct potrace_dpoint_s potrace_dpoint_t;
72
73/* segment tags */
74#define POTRACE_CURVETO 1
75#define POTRACE_CORNER 2
76
77/* closed curve segment */
78struct potrace_curve_s {
79 int n; /* number of segments */
80 int *tag; /* tag[n]: POTRACE_CURVETO or POTRACE_CORNER */
81 potrace_dpoint_t (*c)[3]; /* c[n][3]: control points.
82 c[n][0] is unused for tag[n]=POTRACE_CORNER */
83};
84typedef struct potrace_curve_s potrace_curve_t;
85
86/* Linked list of signed curve segments. Also carries a tree structure. */
87struct potrace_path_s {
88 int area; /* area of the bitmap path */
89 int sign; /* '+' or '-', depending on orientation */
90 potrace_curve_t curve; /* this path's vector data */
91
92 struct potrace_path_s *next; /* linked list structure */
93
94 struct potrace_path_s *childlist; /* tree structure */
95 struct potrace_path_s *sibling; /* tree structure */
96
97 struct potrace_privpath_s *priv; /* private state */
98};
99typedef struct potrace_path_s potrace_path_t;
100
101/* ---------------------------------------------------------------------- */
102/* Potrace state */
103
104#define POTRACE_STATUS_OK 0
105#define POTRACE_STATUS_INCOMPLETE 1
106
107struct potrace_state_s {
108 int status;
109 potrace_path_t *plist; /* vector data */
110
111 struct potrace_privstate_s *priv; /* private state */
112};
113typedef struct potrace_state_s potrace_state_t;
114
115/* ---------------------------------------------------------------------- */
116/* API functions */
117
118/* get default parameters */
119potrace_param_t *potrace_param_default(void);
120
121/* free parameter set */
122void potrace_param_free(potrace_param_t *p);
123
124/* trace a bitmap*/
125potrace_state_t *potrace_trace(const potrace_param_t *param,
126 const potrace_bitmap_t *bm);
127
128/* free a Potrace state */
129void potrace_state_free(potrace_state_t *st);
130
131/* return a static plain text version string identifying this version
132 of potracelib */
133char *potrace_version(void);
134
135#ifdef __cplusplus
136} /* end of extern "C" */
137#endif
138
139#endif /* POTRACELIB_H */
1400
=== removed file 'src/trace/potrace/progress.h'
--- src/trace/potrace/progress.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/progress.h 1970-01-01 00:00:00 +0000
@@ -1,77 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5/* operations on potrace_progress_t objects, which are defined in
6 potracelib.h. Note: the code attempts to minimize runtime overhead
7 when no progress monitoring was requested. It also tries to
8 minimize excessive progress calculations beneath the "epsilon"
9 threshold. */
10
11#ifndef PROGRESS_H
12#define PROGRESS_H
13
14/* structure to hold progress bar callback data */
15struct progress_s {
16 void (*callback)(double progress, void *privdata); /* callback fn */
17 void *data; /* callback function's private data */
18 double min, max; /* desired range of progress, e.g. 0.0 to 1.0 */
19 double epsilon; /* granularity: can skip smaller increments */
20 double b; /* upper limit of subrange in superrange units */
21 double d_prev; /* previous value of d */
22};
23typedef struct progress_s progress_t;
24
25/* notify given progress object of current progress. Note that d is
26 given in the 0.0-1.0 range, which will be scaled and translated to
27 the progress object's range. */
28static inline void progress_update(double d, progress_t *prog) {
29 if (prog != NULL && prog->callback != NULL) {
30 double d_scaled = prog->min * (1-d) + prog->max * d;
31 if (d == 1.0 || d_scaled >= prog->d_prev + prog->epsilon) {
32 prog->callback(prog->min * (1-d) + prog->max * d, prog->data);
33 prog->d_prev = d_scaled;
34 }
35 }
36}
37
38/* start a subrange of the given progress object. The range is
39 narrowed to [a..b], relative to 0.0-1.0 coordinates. If new range
40 is below granularity threshold, disable further subdivisions. */
41static inline void progress_subrange_start(double a, double b, const progress_t *prog, progress_t *sub) {
42 double min, max;
43
44 if (prog == NULL || prog->callback == NULL) {
45 sub->callback = NULL;
46 return;
47 }
48
49 min = prog->min * (1-a) + prog->max * a;
50 max = prog->min * (1-b) + prog->max * b;
51
52 if (max - min < prog->epsilon) {
53 sub->callback = NULL; /* no further progress info in subrange */
54 sub->b = b;
55 return;
56 }
57 sub->callback = prog->callback;
58 sub->data = prog->data;
59 sub->epsilon = prog->epsilon;
60 sub->min = min;
61 sub->max = max;
62 sub->d_prev = prog->d_prev;
63 return;
64}
65
66static inline void progress_subrange_end(progress_t *prog, progress_t *sub) {
67 if (prog != NULL && prog->callback != NULL) {
68 if (sub->callback == NULL) {
69 progress_update(sub->b, prog);
70 } else {
71 prog->d_prev = sub->d_prev;
72 }
73 }
74}
75
76#endif /* PROGRESS_H */
77
780
=== removed file 'src/trace/potrace/render.cpp'
--- src/trace/potrace/render.cpp 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/render.cpp 1970-01-01 00:00:00 +0000
@@ -1,243 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6#include <stdio.h>
7#include <stdlib.h>
8#include <math.h>
9#include <string.h>
10
11#include "render.h"
12#include "greymap.h"
13#include "auxiliary.h"
14
15/* ---------------------------------------------------------------------- */
16/* routines for anti-aliased rendering of curves */
17
18/* we use the following method. Given a point (x,y) (with real-valued
19 coordinates) in the plane, let (xi,yi) be the integer part of the
20 coordinates, i.e., xi=floor(x), yi=floor(y). Define a path from
21 (x,y) to infinity as follows: path(x,y) =
22 (x,y)--(xi+1,y)--(xi+1,yi)--(+infty,yi). Now as the point (x,y)
23 moves smoothly across the plane, the path path(x,y) sweeps
24 (non-smoothly) across a certain area. We proportionately blacken
25 the area as the path moves "downward", and we whiten the area as
26 the path moves "upward". This way, after the point has traversed a
27 closed curve, the interior of the curve has been darkened
28 (counterclockwise movement) or lightened (clockwise movement). (The
29 "grey shift" is actually proportional to the winding number). By
30 choosing the above path with mostly integer coordinates, we achieve
31 that only pixels close to (x,y) receive grey values and are subject
32 to round-off errors. The grey value of pixels far away from (x,y)
33 is always in "integer" (where 0=black, 1=white). As a special
34 trick, we keep an accumulator rm->a1, which holds a double value to
35 be added to the grey value to be added to the current pixel
36 (xi,yi). Only when changing "current" pixels, we convert this
37 double value to an integer. This way we avoid round-off errors at
38 the meeting points of line segments. Another speedup measure is
39 that we sometimes use the rm->incrow_buf array to postpone
40 incrementing or decrementing an entire row. If incrow_buf[y]=x+1!=0,
41 then all the pixels (x,y),(x+1,y),(x+2,y),... are scheduled to be
42 incremented/decremented (which one is the case will be clear from
43 context). This keeps the greymap operations reasonably local. */
44
45/* allocate a new rendering state */
46render_t *render_new(greymap_t *gm) {
47 render_t *rm;
48
49 rm = (render_t *) malloc(sizeof(render_t));
50 if (!rm) {
51 return NULL;
52 }
53 memset(rm, 0, sizeof(render_t));
54 rm->gm = gm;
55 rm->incrow_buf = (int *) calloc(gm->h, sizeof(int));
56 if (!rm->incrow_buf) {
57 free(rm);
58 return NULL;
59 }
60 memset(rm->incrow_buf, 0, gm->h * sizeof(int));
61 return rm;
62}
63
64/* free a given rendering state. Note: this does not free the
65 underlying greymap. */
66void render_free(render_t *rm) {
67 free(rm->incrow_buf);
68 free(rm);
69}
70
71/* close path */
72void render_close(render_t *rm) {
73 if (rm->x0 != rm->x1 || rm->y0 != rm->y1) {
74 render_lineto(rm, rm->x0, rm->y0);
75 }
76 GM_INC(rm->gm, rm->x0i, rm->y0i, (rm->a0+rm->a1)*255);
77
78 /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
79
80 /* the persistent state is now undefined */
81}
82
83/* move point */
84void render_moveto(render_t *rm, double x, double y) {
85 /* close the previous path */
86 render_close(rm);
87
88 rm->x0 = rm->x1 = x;
89 rm->y0 = rm->y1 = y;
90 rm->x0i = (int)floor(rm->x0);
91 rm->x1i = (int)floor(rm->x1);
92 rm->y0i = (int)floor(rm->y0);
93 rm->y1i = (int)floor(rm->y1);
94 rm->a0 = rm->a1 = 0;
95}
96
97/* add b to pixels (x,y) and all pixels to the right of it. However,
98 use rm->incrow_buf as a buffer to economize on multiple calls */
99static void incrow(render_t *rm, int x, int y, int b) {
100 int i, x0;
101
102 if (y < 0 || y >= rm->gm->h) {
103 return;
104 }
105
106 if (x < 0) {
107 x = 0;
108 } else if (x > rm->gm->w) {
109 x = rm->gm->w;
110 }
111 if (rm->incrow_buf[y] == 0) {
112 rm->incrow_buf[y] = x+1; /* store x+1 so that we can use 0 for "vacant" */
113 return;
114 }
115 x0 = rm->incrow_buf[y]-1;
116 rm->incrow_buf[y] = 0;
117 if (x0 < x) {
118 for (i=x0; i<x; i++) {
119 GM_INC(rm->gm, i, y, -b);
120 }
121 } else {
122 for (i=x; i<x0; i++) {
123 GM_INC(rm->gm, i, y, b);
124 }
125 }
126}
127
128/* render a straight line */
129void render_lineto(render_t *rm, double x2, double y2) {
130 int x2i, y2i;
131 double t0=2, s0=2;
132 int sn, tn;
133 double ss=2, ts=2;
134 double r0, r1;
135 int i, j;
136 int rxi, ryi;
137 int s;
138
139 x2i = (int)floor(x2);
140 y2i = (int)floor(y2);
141
142 sn = abs(x2i - rm->x1i);
143 tn = abs(y2i - rm->y1i);
144
145 if (sn) {
146 s0 = ((x2>rm->x1 ? rm->x1i+1 : rm->x1i) - rm->x1)/(x2-rm->x1);
147 ss = fabs(1.0/(x2-rm->x1));
148 }
149 if (tn) {
150 t0 = ((y2>rm->y1 ? rm->y1i+1 : rm->y1i) - rm->y1)/(y2-rm->y1);
151 ts = fabs(1.0/(y2-rm->y1));
152 }
153
154 r0 = 0;
155
156 i = 0;
157 j = 0;
158
159 rxi = rm->x1i;
160 ryi = rm->y1i;
161
162 while (i<sn || j<tn) {
163 if (j>=tn || (i<sn && s0+i*ss < t0+j*ts)) {
164 r1 = s0+i*ss;
165 i++;
166 s = 1;
167 } else {
168 r1 = t0+j*ts;
169 j++;
170 s = 0;
171 }
172 /* render line from r0 to r1 segment of (rm->x1,rm->y1)..(x2,y2) */
173
174 /* move point to r1 */
175 rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
176
177 /* move point across pixel boundary */
178 if (s && x2>rm->x1) {
179 GM_INC(rm->gm, rxi, ryi, rm->a1*255);
180 rm->a1 = 0;
181 rxi++;
182 rm->a1 += rm->y1+r1*(y2-rm->y1)-ryi;
183 } else if (!s && y2>rm->y1) {
184 GM_INC(rm->gm, rxi, ryi, rm->a1*255);
185 rm->a1 = 0;
186 incrow(rm, rxi+1, ryi, 255);
187 ryi++;
188 } else if (s && x2<=rm->x1) {
189 rm->a1 -= rm->y1+r1*(y2-rm->y1)-ryi;
190 GM_INC(rm->gm, rxi, ryi, rm->a1*255);
191 rm->a1 = 0;
192 rxi--;
193 } else if (!s && y2<=rm->y1) {
194 GM_INC(rm->gm, rxi, ryi, rm->a1*255);
195 rm->a1 = 0;
196 ryi--;
197 incrow(rm, rxi+1, ryi, -255);
198 }
199
200 r0 = r1;
201 }
202
203 /* move point to (x2,y2) */
204
205 r1 = 1;
206 rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
207
208 rm->x1i = x2i;
209 rm->y1i = y2i;
210 rm->x1 = x2;
211 rm->y1 = y2;
212
213 /* assert (rxi != rm->x1i || ryi != rm->y1i); */
214}
215
216/* render a Bezier curve. */
217void render_curveto(render_t *rm, double x2, double y2, double x3, double y3, double x4, double y4) {
218 double x1, y1, dd0, dd1, dd, delta, e2, epsilon, t;
219
220 x1 = rm->x1; /* starting point */
221 y1 = rm->y1;
222
223 /* we approximate the curve by small line segments. The interval
224 size, epsilon, is determined on the fly so that the distance
225 between the true curve and its approximation does not exceed the
226 desired accuracy delta. */
227
228 delta = .1; /* desired accuracy, in pixels */
229
230 /* let dd = maximal value of 2nd derivative over curve - this must
231 occur at an endpoint. */
232 dd0 = sq(x1-2*x2+x3) + sq(y1-2*y2+y3);
233 dd1 = sq(x2-2*x3+x4) + sq(y2-2*y3+y4);
234 dd = 6*sqrt(max(dd0, dd1));
235 e2 = 8*delta <= dd ? 8*delta/dd : 1;
236 epsilon = sqrt(e2); /* necessary interval size */
237
238 for (t=epsilon; t<1; t+=epsilon) {
239 render_lineto(rm, x1*cu(1-t)+3*x2*sq(1-t)*t+3*x3*(1-t)*sq(t)+x4*cu(t),
240 y1*cu(1-t)+3*y2*sq(1-t)*t+3*y3*(1-t)*sq(t)+y4*cu(t));
241 }
242 render_lineto(rm, x4, y4);
243}
2440
=== removed file 'src/trace/potrace/render.h'
--- src/trace/potrace/render.h 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/render.h 1970-01-01 00:00:00 +0000
@@ -1,27 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5
6#ifndef RENDER_H
7#define RENDER_H
8
9#include "greymap.h"
10
11struct render_s {
12 greymap_t *gm;
13 double x0, y0, x1, y1;
14 int x0i, y0i, x1i, y1i;
15 double a0, a1;
16 int *incrow_buf;
17};
18typedef struct render_s render_t;
19
20render_t *render_new(greymap_t *gm);
21void render_free(render_t *rm);
22void render_close(render_t *rm);
23void render_moveto(render_t *rm, double x, double y);
24void render_lineto(render_t *rm, double x, double y);
25void render_curveto(render_t *rm, double x2, double y2, double x3, double y3, double x4, double y4);
26
27#endif /* RENDER_H */
280
=== removed file 'src/trace/potrace/trace.cpp'
--- src/trace/potrace/trace.cpp 2015-03-31 10:33:40 +0000
+++ src/trace/potrace/trace.cpp 1970-01-01 00:00:00 +0000
@@ -1,1245 +0,0 @@
1/* Copyright (C) 2001-2015 Peter Selinger.
2 This file is part of Potrace. It is free software and it is covered
3 by the GNU General Public License. See the file COPYING for details. */
4
5/* transform jaggy paths into smooth curves */
6
7#include <stdio.h>
8#include <math.h>
9#include <stdlib.h>
10#include <string.h>
11
12#include "potracelib.h"
13#include "curve.h"
14#include "lists.h"
15#include "auxiliary.h"
16#include "trace.h"
17#include "progress.h"
18
19#define INFTY 10000000 /* it suffices that this is longer than any
20 path; it need not be really infinite */
21#define COS179 -0.999847695156 /* the cosine of 179 degrees */
22
23/* ---------------------------------------------------------------------- */
24#define SAFE_CALLOC(var, n, typ) \
25 if ((var = (typ *)calloc(n, sizeof(typ))) == NULL) goto calloc_error
26
27/* ---------------------------------------------------------------------- */
28/* auxiliary functions */
29
30/* return a direction that is 90 degrees counterclockwise from p2-p0,
31 but then restricted to one of the major wind directions (n, nw, w, etc) */
32static inline point_t dorth_infty(dpoint_t p0, dpoint_t p2) {
33 point_t r;
34
35 r.y = sign(p2.x-p0.x);
36 r.x = -sign(p2.y-p0.y);
37
38 return r;
39}
40
41/* return (p1-p0)x(p2-p0), the area of the parallelogram */
42static inline double dpara(dpoint_t p0, dpoint_t p1, dpoint_t p2) {
43 double x1, y1, x2, y2;
44
45 x1 = p1.x-p0.x;
46 y1 = p1.y-p0.y;
47 x2 = p2.x-p0.x;
48 y2 = p2.y-p0.y;
49
50 return x1*y2 - x2*y1;
51}
52
53/* ddenom/dpara have the property that the square of radius 1 centered
54 at p1 intersects the line p0p2 iff |dpara(p0,p1,p2)| <= ddenom(p0,p2) */
55static inline double ddenom(dpoint_t p0, dpoint_t p2) {
56 point_t r = dorth_infty(p0, p2);
57
58 return r.y*(p2.x-p0.x) - r.x*(p2.y-p0.y);
59}
60
61/* return 1 if a <= b < c < a, in a cyclic sense (mod n) */
62static inline int cyclic(int a, int b, int c) {
63 if (a<=c) {
64 return (a<=b && b<c);
65 } else {
66 return (a<=b || b<c);
67 }
68}
69
70/* determine the center and slope of the line i..j. Assume i<j. Needs
71 "sum" components of p to be set. */
72static void pointslope(privpath_t *pp, int i, int j, dpoint_t *ctr, dpoint_t *dir) {
73 /* assume i<j */
74
75 int n = pp->len;
76 sums_t *sums = pp->sums;
77
78 double x, y, x2, xy, y2;
79 double k;
80 double a, b, c, lambda2, l;
81 int r=0; /* rotations from i to j */
82
83 while (j>=n) {
84 j-=n;
85 r+=1;
86 }
87 while (i>=n) {
88 i-=n;
89 r-=1;
90 }
91 while (j<0) {
92 j+=n;
93 r-=1;
94 }
95 while (i<0) {
96 i+=n;
97 r+=1;
98 }
99
100 x = sums[j+1].x-sums[i].x+r*sums[n].x;
101 y = sums[j+1].y-sums[i].y+r*sums[n].y;
102 x2 = sums[j+1].x2-sums[i].x2+r*sums[n].x2;
103 xy = sums[j+1].xy-sums[i].xy+r*sums[n].xy;
104 y2 = sums[j+1].y2-sums[i].y2+r*sums[n].y2;
105 k = j+1-i+r*n;
106
107 ctr->x = x/k;
108 ctr->y = y/k;
109
110 a = (x2-(double)x*x/k)/k;
111 b = (xy-(double)x*y/k)/k;
112 c = (y2-(double)y*y/k)/k;
113
114 lambda2 = (a+c+sqrt((a-c)*(a-c)+4*b*b))/2; /* larger e.value */
115
116 /* now find e.vector for lambda2 */
117 a -= lambda2;
118 c -= lambda2;
119
120 if (fabs(a) >= fabs(c)) {
121 l = sqrt(a*a+b*b);
122 if (l!=0) {
123 dir->x = -b/l;
124 dir->y = a/l;
125 }
126 } else {
127 l = sqrt(c*c+b*b);
128 if (l!=0) {
129 dir->x = -c/l;
130 dir->y = b/l;
131 }
132 }
133 if (l==0) {
134 dir->x = dir->y = 0; /* sometimes this can happen when k=4:
135 the two eigenvalues coincide */
136 }
137}
138
139/* the type of (affine) quadratic forms, represented as symmetric 3x3
140 matrices. The value of the quadratic form at a vector (x,y) is v^t
141 Q v, where v = (x,y,1)^t. */
142typedef double quadform_t[3][3];
143
144/* Apply quadratic form Q to vector w = (w.x,w.y) */
145static inline double quadform(quadform_t Q, dpoint_t w) {
146 double v[3];
147 int i, j;
148 double sum;
149
150 v[0] = w.x;
151 v[1] = w.y;
152 v[2] = 1;
153 sum = 0.0;
154
155 for (i=0; i<3; i++) {
156 for (j=0; j<3; j++) {
157 sum += v[i] * Q[i][j] * v[j];
158 }
159 }
160 return sum;
161}
162
163/* calculate p1 x p2 */
164static inline int xprod(point_t p1, point_t p2) {
165 return p1.x*p2.y - p1.y*p2.x;
166}
167
168/* calculate (p1-p0)x(p3-p2) */
169static inline double cprod(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3) {
170 double x1, y1, x2, y2;
171
172 x1 = p1.x - p0.x;
173 y1 = p1.y - p0.y;
174 x2 = p3.x - p2.x;
175 y2 = p3.y - p2.y;
176
177 return x1*y2 - x2*y1;
178}
179
180/* calculate (p1-p0)*(p2-p0) */
181static inline double iprod(dpoint_t p0, dpoint_t p1, dpoint_t p2) {
182 double x1, y1, x2, y2;
183
184 x1 = p1.x - p0.x;
185 y1 = p1.y - p0.y;
186 x2 = p2.x - p0.x;
187 y2 = p2.y - p0.y;
188
189 return x1*x2 + y1*y2;
190}
191
192/* calculate (p1-p0)*(p3-p2) */
193static inline double iprod1(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3) {
194 double x1, y1, x2, y2;
195
196 x1 = p1.x - p0.x;
197 y1 = p1.y - p0.y;
198 x2 = p3.x - p2.x;
199 y2 = p3.y - p2.y;
200
201 return x1*x2 + y1*y2;
202}
203
204/* calculate distance between two points */
205static inline double ddist(dpoint_t p, dpoint_t q) {
206 return sqrt(sq(p.x-q.x)+sq(p.y-q.y));
207}
208
209/* calculate point of a bezier curve */
210static inline dpoint_t bezier(double t, dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3) {
211 double s = 1-t;
212 dpoint_t res;
213
214 /* Note: a good optimizing compiler (such as gcc-3) reduces the
215 following to 16 multiplications, using common subexpression
216 elimination. */
217
218 res.x = s*s*s*p0.x + 3*(s*s*t)*p1.x + 3*(t*t*s)*p2.x + t*t*t*p3.x;
219 res.y = s*s*s*p0.y + 3*(s*s*t)*p1.y + 3*(t*t*s)*p2.y + t*t*t*p3.y;
220
221 return res;
222}
223
224/* calculate the point t in [0..1] on the (convex) bezier curve
225 (p0,p1,p2,p3) which is tangent to q1-q0. Return -1.0 if there is no
226 solution in [0..1]. */
227static double tangent(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3, dpoint_t q0, dpoint_t q1) {
228 double A, B, C; /* (1-t)^2 A + 2(1-t)t B + t^2 C = 0 */
229 double a, b, c; /* a t^2 + b t + c = 0 */
230 double d, s, r1, r2;
231
232 A = cprod(p0, p1, q0, q1);
233 B = cprod(p1, p2, q0, q1);
234 C = cprod(p2, p3, q0, q1);
235
236 a = A - 2*B + C;
237 b = -2*A + 2*B;
238 c = A;
239
240 d = b*b - 4*a*c;
241
242 if (a==0 || d<0) {
243 return -1.0;
244 }
245
246 s = sqrt(d);
247
248 r1 = (-b + s) / (2 * a);
249 r2 = (-b - s) / (2 * a);
250
251 if (r1 >= 0 && r1 <= 1) {
252 return r1;
253 } else if (r2 >= 0 && r2 <= 1) {
254 return r2;
255 } else {
256 return -1.0;
257 }
258}
259
260/* ---------------------------------------------------------------------- */
261/* Preparation: fill in the sum* fields of a path (used for later
262 rapid summing). Return 0 on success, 1 with errno set on
263 failure. */
264static int calc_sums(privpath_t *pp) {
265 int i, x, y;
266 int n = pp->len;
267
268 SAFE_CALLOC(pp->sums, pp->len+1, sums_t);
269
270 /* origin */
271 pp->x0 = pp->pt[0].x;
272 pp->y0 = pp->pt[0].y;
273
274 /* preparatory computation for later fast summing */
275 pp->sums[0].x2 = pp->sums[0].xy = pp->sums[0].y2 = pp->sums[0].x = pp->sums[0].y = 0;
276 for (i=0; i<n; i++) {
277 x = pp->pt[i].x - pp->x0;
278 y = pp->pt[i].y - pp->y0;
279 pp->sums[i+1].x = pp->sums[i].x + x;
280 pp->sums[i+1].y = pp->sums[i].y + y;
281 pp->sums[i+1].x2 = pp->sums[i].x2 + x*x;
282 pp->sums[i+1].xy = pp->sums[i].xy + x*y;
283 pp->sums[i+1].y2 = pp->sums[i].y2 + y*y;
284 }
285 return 0;
286
287 calloc_error:
288 return 1;
289}
290
291/* ---------------------------------------------------------------------- */
292/* Stage 1: determine the straight subpaths (Sec. 2.2.1). Fill in the
293 "lon" component of a path object (based on pt/len). For each i,
294 lon[i] is the furthest index such that a straight line can be drawn
295 from i to lon[i]. Return 1 on error with errno set, else 0. */
296
297/* this algorithm depends on the fact that the existence of straight
298 subpaths is a triplewise property. I.e., there exists a straight
299 line through squares i0,...,in iff there exists a straight line
300 through i,j,k, for all i0<=i<j<k<=in. (Proof?) */
301
302/* this implementation of calc_lon is O(n^2). It replaces an older
303 O(n^3) version. A "constraint" means that future points must
304 satisfy xprod(constraint[0], cur) >= 0 and xprod(constraint[1],
305 cur) <= 0. */
306
307/* Remark for Potrace 1.1: the current implementation of calc_lon is
308 more complex than the implementation found in Potrace 1.0, but it
309 is considerably faster. The introduction of the "nc" data structure
310 means that we only have to test the constraints for "corner"
311 points. On a typical input file, this speeds up the calc_lon
312 function by a factor of 31.2, thereby decreasing its time share
313 within the overall Potrace algorithm from 72.6% to 7.82%, and
314 speeding up the overall algorithm by a factor of 3.36. On another
315 input file, calc_lon was sped up by a factor of 6.7, decreasing its
316 time share from 51.4% to 13.61%, and speeding up the overall
317 algorithm by a factor of 1.78. In any case, the savings are
318 substantial. */
319
320/* returns 0 on success, 1 on error with errno set */
321static int calc_lon(privpath_t *pp) {
322 point_t *pt = pp->pt;
323 int n = pp->len;
324 int i, j, k, k1;
325 int ct[4], dir;
326 point_t constraint[2];
327 point_t cur;
328 point_t off;
329 int *pivk = NULL; /* pivk[n] */
330 int *nc = NULL; /* nc[n]: next corner */
331 point_t dk; /* direction of k-k1 */
332 int a, b, c, d;
333
334 SAFE_CALLOC(pivk, n, int);
335 SAFE_CALLOC(nc, n, int);
336
337 /* initialize the nc data structure. Point from each point to the
338 furthest future point to which it is connected by a vertical or
339 horizontal segment. We take advantage of the fact that there is
340 always a direction change at 0 (due to the path decomposition
341 algorithm). But even if this were not so, there is no harm, as
342 in practice, correctness does not depend on the word "furthest"
343 above. */
344 k = 0;
345 for (i=n-1; i>=0; i--) {
346 if (pt[i].x != pt[k].x && pt[i].y != pt[k].y) {
347 k = i+1; /* necessarily i<n-1 in this case */
348 }
349 nc[i] = k;
350 }
351
352 SAFE_CALLOC(pp->lon, n, int);
353
354 /* determine pivot points: for each i, let pivk[i] be the furthest k
355 such that all j with i<j<k lie on a line connecting i,k. */
356
357 for (i=n-1; i>=0; i--) {
358 ct[0] = ct[1] = ct[2] = ct[3] = 0;
359
360 /* keep track of "directions" that have occurred */
361 dir = (3+3*(pt[mod(i+1,n)].x-pt[i].x)+(pt[mod(i+1,n)].y-pt[i].y))/2;
362 ct[dir]++;
363
364 constraint[0].x = 0;
365 constraint[0].y = 0;
366 constraint[1].x = 0;
367 constraint[1].y = 0;
368
369 /* find the next k such that no straight line from i to k */
370 k = nc[i];
371 k1 = i;
372 while (1) {
373
374 dir = (3+3*sign(pt[k].x-pt[k1].x)+sign(pt[k].y-pt[k1].y))/2;
375 ct[dir]++;
376
377 /* if all four "directions" have occurred, cut this path */
378 if (ct[0] && ct[1] && ct[2] && ct[3]) {
379 pivk[i] = k1;
380 goto foundk;
381 }
382
383 cur.x = pt[k].x - pt[i].x;
384 cur.y = pt[k].y - pt[i].y;
385
386 /* see if current constraint is violated */
387 if (xprod(constraint[0], cur) < 0 || xprod(constraint[1], cur) > 0) {
388 goto constraint_viol;
389 }
390
391 /* else, update constraint */
392 if (abs(cur.x) <= 1 && abs(cur.y) <= 1) {
393 /* no constraint */
394 } else {
395 off.x = cur.x + ((cur.y>=0 && (cur.y>0 || cur.x<0)) ? 1 : -1);
396 off.y = cur.y + ((cur.x<=0 && (cur.x<0 || cur.y<0)) ? 1 : -1);
397 if (xprod(constraint[0], off) >= 0) {
398 constraint[0] = off;
399 }
400 off.x = cur.x + ((cur.y<=0 && (cur.y<0 || cur.x<0)) ? 1 : -1);
401 off.y = cur.y + ((cur.x>=0 && (cur.x>0 || cur.y<0)) ? 1 : -1);
402 if (xprod(constraint[1], off) <= 0) {
403 constraint[1] = off;
404 }
405 }
406 k1 = k;
407 k = nc[k1];
408 if (!cyclic(k,i,k1)) {
409 break;
410 }
411 }
412 constraint_viol:
413 /* k1 was the last "corner" satisfying the current constraint, and
414 k is the first one violating it. We now need to find the last
415 point along k1..k which satisfied the constraint. */
416 dk.x = sign(pt[k].x-pt[k1].x);
417 dk.y = sign(pt[k].y-pt[k1].y);
418 cur.x = pt[k1].x - pt[i].x;
419 cur.y = pt[k1].y - pt[i].y;
420 /* find largest integer j such that xprod(constraint[0], cur+j*dk)
421 >= 0 and xprod(constraint[1], cur+j*dk) <= 0. Use bilinearity
422 of xprod. */
423 a = xprod(constraint[0], cur);
424 b = xprod(constraint[0], dk);
425 c = xprod(constraint[1], cur);
426 d = xprod(constraint[1], dk);
427 /* find largest integer j such that a+j*b>=0 and c+j*d<=0. This
428 can be solved with integer arithmetic. */
429 j = INFTY;
430 if (b<0) {
431 j = floordiv(a,-b);
432 }
433 if (d>0) {
434 j = min(j, floordiv(-c,d));
435 }
436 pivk[i] = mod(k1+j,n);
437 foundk:
438 ;
439 } /* for i */
440
441 /* clean up: for each i, let lon[i] be the largest k such that for
442 all i' with i<=i'<k, i'<k<=pivk[i']. */
443
444 j=pivk[n-1];
445 pp->lon[n-1]=j;
446 for (i=n-2; i>=0; i--) {
447 if (cyclic(i+1,pivk[i],j)) {
448 j=pivk[i];
449 }
450 pp->lon[i]=j;
451 }
452
453 for (i=n-1; cyclic(mod(i+1,n),j,pp->lon[i]); i--) {
454 pp->lon[i] = j;
455 }
456
457 free(pivk);
458 free(nc);
459 return 0;
460
461 calloc_error:
462 free(pivk);
463 free(nc);
464 return 1;
465}
466
467
468/* ---------------------------------------------------------------------- */
469/* Stage 2: calculate the optimal polygon (Sec. 2.2.2-2.2.4). */
470
471/* Auxiliary function: calculate the penalty of an edge from i to j in
472 the given path. This needs the "lon" and "sum*" data. */
473
474static double penalty3(privpath_t *pp, int i, int j) {
475 int n = pp->len;
476 point_t *pt = pp->pt;
477 sums_t *sums = pp->sums;
478
479 /* assume 0<=i<j<=n */
480 double x, y, x2, xy, y2;
481 double k;
482 double a, b, c, s;
483 double px, py, ex, ey;
484
485 int r = 0; /* rotations from i to j */
486
487 if (j>=n) {
488 j -= n;
489 r = 1;
490 }
491
492 /* critical inner loop: the "if" gives a 4.6 percent speedup */
493 if (r == 0) {
494 x = sums[j+1].x - sums[i].x;
495 y = sums[j+1].y - sums[i].y;
496 x2 = sums[j+1].x2 - sums[i].x2;
497 xy = sums[j+1].xy - sums[i].xy;
498 y2 = sums[j+1].y2 - sums[i].y2;
499 k = j+1 - i;
500 } else {
501 x = sums[j+1].x - sums[i].x + sums[n].x;
502 y = sums[j+1].y - sums[i].y + sums[n].y;
503 x2 = sums[j+1].x2 - sums[i].x2 + sums[n].x2;
504 xy = sums[j+1].xy - sums[i].xy + sums[n].xy;
505 y2 = sums[j+1].y2 - sums[i].y2 + sums[n].y2;
506 k = j+1 - i + n;
507 }
508
509 px = (pt[i].x + pt[j].x) / 2.0 - pt[0].x;
510 py = (pt[i].y + pt[j].y) / 2.0 - pt[0].y;
511 ey = (pt[j].x - pt[i].x);
512 ex = -(pt[j].y - pt[i].y);
513
514 a = ((x2 - 2*x*px) / k + px*px);
515 b = ((xy - x*py - y*px) / k + px*py);
516 c = ((y2 - 2*y*py) / k + py*py);
517
518 s = ex*ex*a + 2*ex*ey*b + ey*ey*c;
519
520 return sqrt(s);
521}
522
523/* find the optimal polygon. Fill in the m and po components. Return 1
524 on failure with errno set, else 0. Non-cyclic version: assumes i=0
525 is in the polygon. Fixme: implement cyclic version. */
526static int bestpolygon(privpath_t *pp)
527{
528 int i, j, m, k;
529 int n = pp->len;
530 double *pen = NULL; /* pen[n+1]: penalty vector */
531 int *prev = NULL; /* prev[n+1]: best path pointer vector */
532 int *clip0 = NULL; /* clip0[n]: longest segment pointer, non-cyclic */
533 int *clip1 = NULL; /* clip1[n+1]: backwards segment pointer, non-cyclic */
534 int *seg0 = NULL; /* seg0[m+1]: forward segment bounds, m<=n */
535 int *seg1 = NULL; /* seg1[m+1]: backward segment bounds, m<=n */
536 double thispen;
537 double best;
538 int c;
539
540 SAFE_CALLOC(pen, n+1, double);
541 SAFE_CALLOC(prev, n+1, int);
542 SAFE_CALLOC(clip0, n, int);
543 SAFE_CALLOC(clip1, n+1, int);
544 SAFE_CALLOC(seg0, n+1, int);
545 SAFE_CALLOC(seg1, n+1, int);
546
547 /* calculate clipped paths */
548 for (i=0; i<n; i++) {
549 c = mod(pp->lon[mod(i-1,n)]-1,n);
550 if (c == i) {
551 c = mod(i+1,n);
552 }
553 if (c < i) {
554 clip0[i] = n;
555 } else {
556 clip0[i] = c;
557 }
558 }
559
560 /* calculate backwards path clipping, non-cyclic. j <= clip0[i] iff
561 clip1[j] <= i, for i,j=0..n. */
562 j = 1;