KiCad PCB EDA Suite
decompose.cpp File Reference
#include <cstdint>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bitmap.h"
#include "curve.h"
#include "decompose.h"
#include "lists.h"
#include "potracelib.h"
#include "progress.h"

Go to the source code of this file.

Classes

struct  bbox_s
 

Typedefs

typedef struct bbox_s bbox_t
 

Functions

static int detrand (int x, int y)
 
static void bm_clearexcess (potrace_bitmap_t *bm)
 
static void clear_bm_with_bbox (potrace_bitmap_t *bm, bbox_t *bbox)
 
static int majority (potrace_bitmap_t *bm, int x, int y)
 
static void xor_to_ref (potrace_bitmap_t *bm, int x, int y, int xa)
 
static void xor_path (potrace_bitmap_t *bm, path_t *p)
 
static void setbbox_path (bbox_t *bbox, path_t *p)
 
static path_tfindpath (potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy)
 
static void pathlist_to_tree (path_t *plist, potrace_bitmap_t *bm)
 
static int findnext (potrace_bitmap_t *bm, int *xp, int *yp)
 
int bm_to_pathlist (const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress)
 

Typedef Documentation

typedef struct bbox_s bbox_t

Definition at line 81 of file decompose.cpp.

Function Documentation

static void bm_clearexcess ( potrace_bitmap_t bm)
static

Definition at line 60 of file decompose.cpp.

References BM_ALLBITS, bm_index, BM_WORDBITS, potrace_bitmap_s::h, and potrace_bitmap_s::w.

Referenced by bm_to_pathlist().

61 {
62  potrace_word mask;
63  int y;
64 
65  if( bm->w % BM_WORDBITS != 0 )
66  {
67  mask = BM_ALLBITS << ( BM_WORDBITS - ( bm->w % BM_WORDBITS ) );
68 
69  for( y = 0; y < bm->h; y++ )
70  {
71  *bm_index( bm, bm->w, y ) &= mask;
72  }
73  }
74 }
#define bm_index(bm, x, y)
Definition: bitmap.h:33
unsigned long potrace_word
Definition: potracelib.h:53
#define BM_WORDBITS
Definition: bitmap.h:25
#define BM_ALLBITS
Definition: bitmap.h:27
int bm_to_pathlist ( const potrace_bitmap_t bm,
path_t **  plistp,
const potrace_param_t param,
progress_t progress 
)

Definition at line 565 of file decompose.cpp.

References potrace_path_s::area, bm_clearexcess(), bm_dup(), bm_free(), BM_GET, findnext(), findpath(), potrace_bitmap_s::h, list_forall_unlink, list_insert_beforehook, path_free(), pathlist_to_tree(), progress_update(), sign(), potrace_param_s::turdsize, potrace_param_s::turnpolicy, and xor_path().

Referenced by potrace_trace().

567 {
568  int x;
569  int y;
570  path_t* p;
571  path_t* plist = NULL; /* linked list of path objects */
572  path_t** plist_hook = &plist; /* used to speed up appending to linked list */
573  potrace_bitmap_t* bm1 = NULL;
574  int sign;
575 
576  bm1 = bm_dup( bm );
577 
578  if( !bm1 )
579  {
580  goto error;
581  }
582 
583  /* be sure the byte padding on the right is set to 0, as the fast
584  * pixel search below relies on it */
585  bm_clearexcess( bm1 );
586 
587  /* iterate through components */
588  x = 0;
589  y = bm1->h - 1;
590 
591  while( findnext( bm1, &x, &y ) == 0 )
592  {
593  /* calculate the sign by looking at the original */
594  sign = BM_GET( bm, x, y ) ? '+' : '-';
595 
596  /* calculate the path */
597  p = findpath( bm1, x, y + 1, sign, param->turnpolicy );
598 
599  if( p == NULL )
600  {
601  goto error;
602  }
603 
604  /* update buffered image */
605  xor_path( bm1, p );
606 
607  /* if it's a turd, eliminate it, else append it to the list */
608  if( p->area <= param->turdsize )
609  {
610  path_free( p );
611  }
612  else
613  {
614  list_insert_beforehook( p, plist_hook );
615  }
616 
617  if( bm1->h > 0 )
618  {
619  /* to be sure */
620  progress_update( 1 - y / (double) bm1->h, progress );
621  }
622  }
623 
624  pathlist_to_tree( plist, bm1 );
625  bm_free( bm1 );
626  *plistp = plist;
627 
628  progress_update( 1.0, progress );
629 
630  return 0;
631 
632 error:
633  bm_free( bm1 );
634  list_forall_unlink( p, plist ) {
635  path_free( p );
636  }
637  return -1;
638 }
static void bm_free(potrace_bitmap_t *bm)
Definition: bitmap.h:102
#define list_forall_unlink(elt, list)
Definition: lists.h:186
static potrace_bitmap_t * bm_dup(const potrace_bitmap_t *bm)
Definition: bitmap.h:170
static path_t * findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy)
Definition: decompose.cpp:255
static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm)
Definition: decompose.cpp:382
#define BM_GET(bm, x, y)
Definition: bitmap.h:42
static int findnext(potrace_bitmap_t *bm, int *xp, int *yp)
Definition: decompose.cpp:526
void path_free(path_t *p)
Definition: curve.cpp:58
static void bm_clearexcess(potrace_bitmap_t *bm)
Definition: decompose.cpp:60
static void xor_path(potrace_bitmap_t *bm, path_t *p)
Definition: decompose.cpp:180
static void progress_update(double d, progress_t *prog)
Definition: progress.h:29
#define list_insert_beforehook(elt, hook)
Definition: lists.h:79
int sign(T val)
Definition: math_util.h:44
static void clear_bm_with_bbox ( potrace_bitmap_t bm,
bbox_t bbox 
)
static

Definition at line 85 of file decompose.cpp.

References bm_scanline, BM_WORDBITS, bbox_s::x0, bbox_s::x1, bbox_s::y0, and bbox_s::y1.

Referenced by pathlist_to_tree().

86 {
87  int imin = ( bbox->x0 / BM_WORDBITS );
88  int imax = ( ( bbox->x1 + BM_WORDBITS - 1 ) / BM_WORDBITS );
89  int i, y;
90 
91  for( y = bbox->y0; y < bbox->y1; y++ )
92  {
93  for( i = imin; i < imax; i++ )
94  {
95  bm_scanline( bm, y )[i] = 0;
96  }
97  }
98 }
int x1
Definition: decompose.cpp:79
int y0
Definition: decompose.cpp:79
#define bm_scanline(bm, y)
Definition: bitmap.h:32
int x0
Definition: decompose.cpp:79
#define BM_WORDBITS
Definition: bitmap.h:25
static int detrand ( int  x,
int  y 
)
inlinestatic

Definition at line 29 of file decompose.cpp.

Referenced by findpath().

30 {
31  unsigned int z;
32  static const unsigned char t[256] =
33  {
34  /* non-linear sequence: constant term of inverse in GF(8),
35  * mod x^8+x^4+x^3+x+1 */
36  0,
37  1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0,
38  0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1,
39  1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0,
40  1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1,
41  0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
42  1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0,
43  1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1,
44  0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1,
45  0, 1, 0, 1, 0, 1, 0,
46  };
47 
48  /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible
49  * 5-bit sequence */
50  z = ( ( 0x04b3e375 * x ) ^ y ) * 0x05a8ef93;
51  z = t[z & 0xff] ^ t[( z >> 8 ) & 0xff] ^ t[( z >> 16 ) & 0xff] ^ t[( z >> 24 ) & 0xff];
52  return z;
53 }
static int findnext ( potrace_bitmap_t bm,
int *  xp,
int *  yp 
)
static

Definition at line 526 of file decompose.cpp.

References BM_GET, bm_index, BM_WORDBITS, potrace_bitmap_s::w, and bbox_s::x0.

Referenced by bm_to_pathlist().

527 {
528  int x;
529  int y;
530  int x0;
531 
532  x0 = ( *xp ) & ~( BM_WORDBITS - 1 );
533 
534  for( y = *yp; y >= 0; y-- )
535  {
536  for( x = x0; x < bm->w && x >= 0; x += (unsigned) BM_WORDBITS )
537  {
538  if( *bm_index( bm, x, y ) )
539  {
540  while( !BM_GET( bm, x, y ) )
541  {
542  x++;
543  }
544 
545  /* found */
546  *xp = x;
547  *yp = y;
548  return 0;
549  }
550  }
551 
552  x0 = 0;
553  }
554 
555  /* not found */
556  return 1;
557 }
#define bm_index(bm, x, y)
Definition: bitmap.h:33
#define BM_GET(bm, x, y)
Definition: bitmap.h:42
#define BM_WORDBITS
Definition: bitmap.h:25
static path_t* findpath ( potrace_bitmap_t bm,
int  x0,
int  y0,
int  sign,
int  turnpolicy 
)
static

Definition at line 255 of file decompose.cpp.

References potrace_path_s::area, BM_GET, detrand(), potrace_privpath_s::len, majority(), path_new(), POTRACE_TURNPOLICY_BLACK, POTRACE_TURNPOLICY_MAJORITY, POTRACE_TURNPOLICY_MINORITY, POTRACE_TURNPOLICY_RANDOM, POTRACE_TURNPOLICY_RIGHT, POTRACE_TURNPOLICY_WHITE, potrace_path_s::priv, potrace_privpath_s::pt, sign(), potrace_path_s::sign, point_s::x, bbox_s::x0, point_s::y, and bbox_s::y0.

Referenced by bm_to_pathlist().

256 {
257  int x, y, dirx, diry, len, size;
258  uint64_t area;
259  int c, d, tmp;
260  point_t* pt, * pt1;
261  path_t* p = NULL;
262 
263  x = x0;
264  y = y0;
265  dirx = 0;
266  diry = -1;
267 
268  len = size = 0;
269  pt = NULL;
270  area = 0;
271 
272  while( 1 )
273  {
274  /* add point to path */
275  if( len >= size )
276  {
277  size += 100;
278  size = (int) ( 1.3 * size );
279  pt1 = (point_t*) realloc( pt, size * sizeof( point_t ) );
280 
281  if( !pt1 )
282  {
283  goto error;
284  }
285 
286  pt = pt1;
287  }
288 
289  pt[len].x = x;
290  pt[len].y = y;
291  len++;
292 
293  /* move to next point */
294  x += dirx;
295  y += diry;
296  area += x * diry;
297 
298  /* path complete? */
299  if( x == x0 && y == y0 )
300  {
301  break;
302  }
303 
304  /* determine next direction */
305  c = BM_GET( bm, x + ( dirx + diry - 1 ) / 2, y + ( diry - dirx - 1 ) / 2 );
306  d = BM_GET( bm, x + ( dirx - diry - 1 ) / 2, y + ( diry + dirx - 1 ) / 2 );
307 
308  if( c && !d )
309  {
310  /* ambiguous turn */
311  if( turnpolicy == POTRACE_TURNPOLICY_RIGHT
312  || ( turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+' )
313  || ( turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-' )
314  || ( turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand( x, y ) )
315  || ( turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority( bm, x, y ) )
316  || ( turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority( bm, x, y ) ) )
317  {
318  tmp = dirx; /* right turn */
319  dirx = diry;
320  diry = -tmp;
321  }
322  else
323  {
324  tmp = dirx; /* left turn */
325  dirx = -diry;
326  diry = tmp;
327  }
328  }
329  else if( c )
330  {
331  /* right turn */
332  tmp = dirx;
333  dirx = diry;
334  diry = -tmp;
335  }
336  else if( !d )
337  {
338  /* left turn */
339  tmp = dirx;
340  dirx = -diry;
341  diry = tmp;
342  }
343  } /* while this path */
344 
345  /* allocate new path object */
346  p = path_new();
347 
348  if( !p )
349  {
350  goto error;
351  }
352 
353  p->priv->pt = pt;
354  p->priv->len = len;
355  p->area = area <= INT_MAX ? area : INT_MAX; /* avoid overflow */
356  p->sign = sign;
357 
358  return p;
359 
360 error:
361  free( pt );
362  return NULL;
363 }
long y
Definition: auxiliary.h:25
path_t * path_new(void)
Definition: curve.cpp:26
static int majority(potrace_bitmap_t *bm, int x, int y)
Definition: decompose.cpp:106
#define POTRACE_TURNPOLICY_RIGHT
Definition: potracelib.h:22
#define BM_GET(bm, x, y)
Definition: bitmap.h:42
long x
Definition: auxiliary.h:24
struct potrace_privpath_s * priv
Definition: potracelib.h:103
#define POTRACE_TURNPOLICY_RANDOM
Definition: potracelib.h:25
static int detrand(int x, int y)
Definition: decompose.cpp:29
#define POTRACE_TURNPOLICY_MINORITY
Definition: potracelib.h:23
point_t * pt
Definition: curve.h:53
#define POTRACE_TURNPOLICY_BLACK
Definition: potracelib.h:19
#define POTRACE_TURNPOLICY_MAJORITY
Definition: potracelib.h:24
#define POTRACE_TURNPOLICY_WHITE
Definition: potracelib.h:20
int sign(T val)
Definition: math_util.h:44
static int majority ( potrace_bitmap_t bm,
int  x,
int  y 
)
static

Definition at line 106 of file decompose.cpp.

References BM_GET.

Referenced by findpath().

107 {
108  int i, a, ct;
109 
110  for( i = 2; i < 5; i++ )
111  {
112  /* check at "radius" i */
113  ct = 0;
114 
115  for( a = -i + 1; a <= i - 1; a++ )
116  {
117  ct += BM_GET( bm, x + a, y + i - 1 ) ? 1 : -1;
118  ct += BM_GET( bm, x + i - 1, y + a - 1 ) ? 1 : -1;
119  ct += BM_GET( bm, x + a - 1, y - i ) ? 1 : -1;
120  ct += BM_GET( bm, x - i, y + a ) ? 1 : -1;
121  }
122 
123  if( ct > 0 )
124  {
125  return 1;
126  }
127  else if( ct < 0 )
128  {
129  return 0;
130  }
131  }
132 
133  return 0;
134 }
#define BM_GET(bm, x, y)
Definition: bitmap.h:42
static void pathlist_to_tree ( path_t plist,
potrace_bitmap_t bm 
)
static

Definition at line 382 of file decompose.cpp.

References bm_clear(), BM_GET, potrace_path_s::childlist, clear_bm_with_bbox(), list_append, list_forall, list_forall_unlink, list_insert_beforehook, potrace_path_s::next, potrace_path_s::priv, potrace_privpath_s::pt, setbbox_path(), potrace_path_s::sibling, point_s::x, xor_path(), point_s::y, and bbox_s::y0.

Referenced by bm_to_pathlist().

383 {
384  path_t* p, * p1;
385  path_t* heap, * heap1;
386  path_t* cur;
387  path_t* head;
388  path_t** plist_hook; /* for fast appending to linked list */
389  path_t** hook_in, ** hook_out; /* for fast appending to linked list */
390  bbox_t bbox;
391 
392  bm_clear( bm, 0 );
393 
394  /* save original "next" pointers */
395  list_forall( p, plist ) {
396  p->sibling = p->next;
397  p->childlist = NULL;
398  }
399 
400  heap = plist;
401 
402  /* the heap holds a list of lists of paths. Use "childlist" field
403  * for outer list, "next" field for inner list. Each of the sublists
404  * is to be turned into a tree. This code is messy, but it is
405  * actually fast. Each path is rendered exactly once. We use the
406  * heap to get a tail recursive algorithm: the heap holds a list of
407  * pathlists which still need to be transformed. */
408 
409  while( heap )
410  {
411  /* unlink first sublist */
412  cur = heap;
413  heap = heap->childlist;
414  cur->childlist = NULL;
415 
416  /* unlink first path */
417  head = cur;
418  cur = cur->next;
419  head->next = NULL;
420 
421  /* render path */
422  xor_path( bm, head );
423  setbbox_path( &bbox, head );
424 
425  /* now do insideness test for each element of cur; append it to
426  * head->childlist if it's inside head, else append it to
427  * head->next. */
428  hook_in = &head->childlist;
429  hook_out = &head->next;
430  list_forall_unlink( p, cur ) {
431  if( p->priv->pt[0].y <= bbox.y0 )
432  {
433  list_insert_beforehook( p, hook_out );
434  /* append the remainder of the list to hook_out */
435  *hook_out = cur;
436  break;
437  }
438 
439  if( BM_GET( bm, p->priv->pt[0].x, p->priv->pt[0].y - 1 ) )
440  {
441  list_insert_beforehook( p, hook_in );
442  }
443  else
444  {
445  list_insert_beforehook( p, hook_out );
446  }
447  }
448 
449  /* clear bm */
450  clear_bm_with_bbox( bm, &bbox );
451 
452  /* now schedule head->childlist and head->next for further
453  * processing */
454  if( head->next )
455  {
456  head->next->childlist = heap;
457  heap = head->next;
458  }
459 
460  if( head->childlist )
461  {
462  head->childlist->childlist = heap;
463  heap = head->childlist;
464  }
465  }
466 
467  /* copy sibling structure from "next" to "sibling" component */
468  p = plist;
469 
470  while( p )
471  {
472  p1 = p->sibling;
473  p->sibling = p->next;
474  p = p1;
475  }
476 
477  /* reconstruct a new linked list ("next") structure from tree
478  * ("childlist", "sibling") structure. This code is slightly messy,
479  * because we use a heap to make it tail recursive: the heap
480  * contains a list of childlists which still need to be
481  * processed. */
482  heap = plist;
483 
484  if( heap )
485  {
486  heap->next = NULL; /* heap is a linked list of childlists */
487  }
488 
489  plist = NULL;
490  plist_hook = &plist;
491 
492  while( heap )
493  {
494  heap1 = heap->next;
495 
496  for( p = heap; p; p = p->sibling )
497  {
498  /* p is a positive path */
499  /* append to linked list */
500  list_insert_beforehook( p, plist_hook );
501 
502  /* go through its children */
503  for( p1 = p->childlist; p1; p1 = p1->sibling )
504  {
505  /* append to linked list */
506  list_insert_beforehook( p1, plist_hook );
507 
508  /* append its childlist to heap, if non-empty */
509  if( p1->childlist )
510  {
511  list_append( path_t, heap1, p1->childlist );
512  }
513  }
514  }
515 
516  heap = heap1;
517  }
518 }
long y
Definition: auxiliary.h:25
int y0
Definition: decompose.cpp:79
#define list_forall_unlink(elt, list)
Definition: lists.h:186
static void setbbox_path(bbox_t *bbox, path_t *p)
Definition: decompose.cpp:211
struct potrace_path_s * childlist
Definition: potracelib.h:100
#define BM_GET(bm, x, y)
Definition: bitmap.h:42
long x
Definition: auxiliary.h:24
struct potrace_path_s * next
Definition: potracelib.h:98
struct potrace_privpath_s * priv
Definition: potracelib.h:103
static void clear_bm_with_bbox(potrace_bitmap_t *bm, bbox_t *bbox)
Definition: decompose.cpp:85
static void xor_path(potrace_bitmap_t *bm, path_t *p)
Definition: decompose.cpp:180
static void bm_clear(potrace_bitmap_t *bm, int c)
Definition: bitmap.h:158
#define list_forall(elt, list)
Definition: lists.h:44
#define list_append(listtype, list, elt)
Definition: lists.h:113
point_t * pt
Definition: curve.h:53
struct potrace_path_s * sibling
Definition: potracelib.h:101
#define list_insert_beforehook(elt, hook)
Definition: lists.h:79
static void setbbox_path ( bbox_t bbox,
path_t p 
)
static

Definition at line 211 of file decompose.cpp.

References potrace_privpath_s::len, potrace_path_s::priv, potrace_privpath_s::pt, point_s::x, bbox_s::x0, bbox_s::x1, point_s::y, bbox_s::y0, and bbox_s::y1.

Referenced by pathlist_to_tree().

212 {
213  int x, y;
214  int k;
215 
216  bbox->y0 = INT_MAX;
217  bbox->y1 = 0;
218  bbox->x0 = INT_MAX;
219  bbox->x1 = 0;
220 
221  for( k = 0; k < p->priv->len; k++ )
222  {
223  x = p->priv->pt[k].x;
224  y = p->priv->pt[k].y;
225 
226  if( x < bbox->x0 )
227  {
228  bbox->x0 = x;
229  }
230 
231  if( x > bbox->x1 )
232  {
233  bbox->x1 = x;
234  }
235 
236  if( y < bbox->y0 )
237  {
238  bbox->y0 = y;
239  }
240 
241  if( y > bbox->y1 )
242  {
243  bbox->y1 = y;
244  }
245  }
246 }
long y
Definition: auxiliary.h:25
int x1
Definition: decompose.cpp:79
int y0
Definition: decompose.cpp:79
long x
Definition: auxiliary.h:24
struct potrace_privpath_s * priv
Definition: potracelib.h:103
int y1
Definition: decompose.cpp:79
int x0
Definition: decompose.cpp:79
point_t * pt
Definition: curve.h:53
static void xor_path ( potrace_bitmap_t bm,
path_t p 
)
static

Definition at line 180 of file decompose.cpp.

References BM_WORDBITS, potrace_privpath_s::len, min, potrace_path_s::priv, potrace_privpath_s::pt, point_s::x, xor_to_ref(), point_s::y, and bbox_s::y1.

Referenced by bm_to_pathlist(), and pathlist_to_tree().

181 {
182  int xa, x, y, k, y1;
183 
184  if( p->priv->len <= 0 )
185  {
186  /* a path of length 0 is silly, but legal */
187  return;
188  }
189 
190  y1 = p->priv->pt[p->priv->len - 1].y;
191 
192  xa = p->priv->pt[0].x & - BM_WORDBITS;
193 
194  for( k = 0; k < p->priv->len; k++ )
195  {
196  x = p->priv->pt[k].x;
197  y = p->priv->pt[k].y;
198 
199  if( y != y1 )
200  {
201  /* efficiently invert the rectangle [x,xa] x [y,y1] */
202  xor_to_ref( bm, x, min( y, y1 ), xa );
203  y1 = y;
204  }
205  }
206 }
long y
Definition: auxiliary.h:25
static void xor_to_ref(potrace_bitmap_t *bm, int x, int y, int xa)
Definition: decompose.cpp:142
long x
Definition: auxiliary.h:24
struct potrace_privpath_s * priv
Definition: potracelib.h:103
point_t * pt
Definition: curve.h:53
#define BM_WORDBITS
Definition: bitmap.h:25
#define min(a, b)
Definition: auxiliary.h:85
static void xor_to_ref ( potrace_bitmap_t bm,
int  x,
int  y,
int  xa 
)
static

Definition at line 142 of file decompose.cpp.

References BM_ALLBITS, bm_index, and BM_WORDBITS.

Referenced by xor_path().

143 {
144  int xhi = x & - BM_WORDBITS;
145  int xlo = x & ( BM_WORDBITS - 1 ); /* = x % BM_WORDBITS */
146  int i;
147 
148  if( xhi < xa )
149  {
150  for( i = xhi; i < xa; i += BM_WORDBITS )
151  {
152  *bm_index( bm, i, y ) ^= BM_ALLBITS;
153  }
154  }
155  else
156  {
157  for( i = xa; i < xhi; i += BM_WORDBITS )
158  {
159  *bm_index( bm, i, y ) ^= BM_ALLBITS;
160  }
161  }
162 
163  /* note: the following "if" is needed because x86 treats a<<b as
164  * a<<(b&31). I spent hours looking for this bug. */
165  if( xlo )
166  {
167  *bm_index( bm, xhi, y ) ^= ( BM_ALLBITS << ( BM_WORDBITS - xlo ) );
168  }
169 }
#define bm_index(bm, x, y)
Definition: bitmap.h:33
#define BM_WORDBITS
Definition: bitmap.h:25
#define BM_ALLBITS
Definition: bitmap.h:27