KiCad PCB EDA Suite
bitmap.h
Go to the documentation of this file.
1 /* Copyright (C) 2001-2017 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 BITMAP_H
6 #define BITMAP_H
7 
8 #include <errno.h>
9 #include <stddef.h>
10 #include <stdlib.h>
11 #include <string.h>
12 
13 /* The bitmap type is defined in potracelib.h */
14 #include "potracelib.h"
15 
16 /* The present file defines some convenient macros and static inline
17  * functions for accessing bitmaps. Since they only produce inline
18  * code, they can be conveniently shared by the library and frontends,
19  * if desired */
20 
21 /* ---------------------------------------------------------------------- */
22 /* some measurements */
23 
24 #define BM_WORDSIZE ( (int) sizeof( potrace_word ) )
25 #define BM_WORDBITS ( 8 * BM_WORDSIZE )
26 #define BM_HIBIT ( ( (potrace_word) 1 ) << ( BM_WORDBITS - 1 ) )
27 #define BM_ALLBITS ( ~(potrace_word) 0 )
28 
29 /* macros for accessing pixel at index (x,y). U* macros omit the
30  * bounds check. */
31 
32 #define bm_scanline( bm, y ) ( ( bm )->map + (ptrdiff_t) ( y ) * (ptrdiff_t) ( bm )->dy )
33 #define bm_index( bm, x, y ) ( &bm_scanline( bm, y )[( x ) / BM_WORDBITS] )
34 #define bm_mask( x ) ( BM_HIBIT >> ( ( x ) & ( BM_WORDBITS - 1 ) ) )
35 #define bm_range( x, a ) ( (int) ( x ) >= 0 && (int) ( x ) < ( a ) )
36 #define bm_safe( bm, x, y ) ( bm_range( x, ( bm )->w ) && bm_range( y, ( bm )->h ) )
37 #define BM_UGET( bm, x, y ) ( ( *bm_index( bm, x, y ) & bm_mask( x ) ) != 0 )
38 #define BM_USET( bm, x, y ) ( *bm_index( bm, x, y ) |= bm_mask( x ) )
39 #define BM_UCLR( bm, x, y ) ( *bm_index( bm, x, y ) &= ~bm_mask( x ) )
40 #define BM_UINV( bm, x, y ) ( *bm_index( bm, x, y ) ^= bm_mask( x ) )
41 #define BM_UPUT( bm, x, y, b ) ( ( b ) ? BM_USET( bm, x, y ) : BM_UCLR( bm, x, y ) )
42 #define BM_GET( bm, x, y ) ( bm_safe( bm, x, y ) ? BM_UGET( bm, x, y ) : 0 )
43 #define BM_SET( bm, x, y ) ( bm_safe( bm, x, y ) ? BM_USET( bm, x, y ) : 0 )
44 #define BM_CLR( bm, x, y ) ( bm_safe( bm, x, y ) ? BM_UCLR( bm, x, y ) : 0 )
45 #define BM_INV( bm, x, y ) ( bm_safe( bm, x, y ) ? BM_UINV( bm, x, y ) : 0 )
46 #define BM_PUT( bm, x, y, b ) ( bm_safe( bm, x, y ) ? BM_UPUT( bm, x, y, b ) : 0 )
47 
48 /* calculate the size, in bytes, required for the data area of a
49  * bitmap of the given dy and h. Assume h >= 0. Return -1 if the size
50  * does not fit into the ptrdiff_t type. */
51 static inline ptrdiff_t getsize( int dy, int h )
52 {
53  ptrdiff_t size;
54 
55  if( dy < 0 )
56  {
57  dy = -dy;
58  }
59 
60  size = (ptrdiff_t) dy * (ptrdiff_t) h * (ptrdiff_t) BM_WORDSIZE;
61 
62  /* check for overflow error */
63  if( size < 0 || ( h != 0 && dy != 0 && size / h / dy != BM_WORDSIZE ) )
64  {
65  return -1;
66  }
67 
68  return size;
69 }
70 
71 
72 /* return the size, in bytes, of the data area of the bitmap. Return
73  * -1 if the size does not fit into the ptrdiff_t type; however, this
74  * cannot happen if the bitmap is well-formed, i.e., if created with
75  * bm_new or bm_dup. */
76 static inline ptrdiff_t bm_size( const potrace_bitmap_t* bm )
77 {
78  return getsize( bm->dy, bm->h );
79 }
80 
81 
82 /* calculate the base address of the bitmap data. Assume that the
83  * bitmap is well-formed, i.e., its size fits into the ptrdiff_t type.
84  * This is the case if created with bm_new or bm_dup. The base address
85  * may differ from bm->map if dy is negative */
86 static inline potrace_word* bm_base( const potrace_bitmap_t* bm )
87 {
88  int dy = bm->dy;
89 
90  if( dy >= 0 || bm->h == 0 )
91  {
92  return bm->map;
93  }
94  else
95  {
96  return bm_scanline( bm, bm->h - 1 );
97  }
98 }
99 
100 
101 /* free the given bitmap. Leaves errno untouched. */
102 static inline void bm_free( potrace_bitmap_t* bm )
103 {
104  if( bm && bm->map )
105  {
106  free( bm_base( bm ) );
107  }
108 
109  free( bm );
110 }
111 
112 
113 /* return new bitmap initialized to 0. NULL with errno on error.
114  * Assumes w, h >= 0. */
115 static inline potrace_bitmap_t* bm_new( int w, int h )
116 {
117  potrace_bitmap_t* bm;
118  int dy = w == 0 ? 0 : ( w - 1 ) / BM_WORDBITS + 1;
119  ptrdiff_t size;
120 
121  size = getsize( dy, h );
122 
123  if( size < 0 )
124  {
125  errno = ENOMEM;
126  return NULL;
127  }
128 
129  if( size == 0 )
130  {
131  size = 1; /* make sure calloc() doesn't return NULL */
132  }
133 
134  bm = (potrace_bitmap_t*) malloc( sizeof( potrace_bitmap_t ) );
135 
136  if( !bm )
137  {
138  return NULL;
139  }
140 
141  bm->w = w;
142  bm->h = h;
143  bm->dy = dy;
144  bm->map = (potrace_word*) calloc( 1, size );
145 
146  if( !bm->map )
147  {
148  free( bm );
149  return NULL;
150  }
151 
152  return bm;
153 }
154 
155 
156 /* clear the given bitmap. Set all bits to c. Assumes a well-formed
157  * bitmap. */
158 static inline void bm_clear( potrace_bitmap_t* bm, int c )
159 {
160  /* Note: if the bitmap was created with bm_new, then it is
161  * guaranteed that size will fit into the ptrdiff_t type. */
162  ptrdiff_t size = bm_size( bm );
163 
164  memset( bm_base( bm ), c ? -1 : 0, size );
165 }
166 
167 
168 /* duplicate the given bitmap. Return NULL on error with errno
169  * set. Assumes a well-formed bitmap. */
170 static inline potrace_bitmap_t* bm_dup( const potrace_bitmap_t* bm )
171 {
172  potrace_bitmap_t* bm1 = bm_new( bm->w, bm->h );
173  int y;
174 
175  if( !bm1 )
176  {
177  return NULL;
178  }
179 
180  for( y = 0; y < bm->h; y++ )
181  {
182  memcpy( bm_scanline( bm1, y ), bm_scanline( bm, y ),
183  (size_t) bm1->dy * (size_t) BM_WORDSIZE );
184  }
185 
186  return bm1;
187 }
188 
189 
190 /* invert the given bitmap. */
191 static inline void bm_invert( potrace_bitmap_t* bm )
192 {
193  int dy = bm->dy;
194  int y;
195  int i;
196  potrace_word* p;
197 
198  if( dy < 0 )
199  {
200  dy = -dy;
201  }
202 
203  for( y = 0; y < bm->h; y++ )
204  {
205  p = bm_scanline( bm, y );
206 
207  for( i = 0; i < dy; i++ )
208  {
209  p[i] ^= BM_ALLBITS;
210  }
211  }
212 }
213 
214 
215 /* turn the given bitmap upside down. This does not move the bitmap
216  * data or change the bm_base() address. */
217 static inline void bm_flip( potrace_bitmap_t* bm )
218 {
219  int dy = bm->dy;
220 
221  if( bm->h == 0 || bm->h == 1 )
222  {
223  return;
224  }
225 
226  bm->map = bm_scanline( bm, bm->h - 1 );
227  bm->dy = -dy;
228 }
229 
230 
231 /* resize the bitmap to the given new height. The bitmap data remains
232  * bottom-aligned (truncated at the top) when dy >= 0 and top-aligned
233  * (truncated at the bottom) when dy < 0. Return 0 on success, or 1 on
234  * error with errno set. If the new height is <= the old one, no error
235  * should occur. If the new height is larger, the additional bitmap
236  * data is *not* initialized. */
237 static inline int bm_resize( potrace_bitmap_t* bm, int h )
238 {
239  int dy = bm->dy;
240  ptrdiff_t newsize;
241  potrace_word* newmap;
242 
243  if( dy < 0 )
244  {
245  bm_flip( bm );
246  }
247 
248  newsize = getsize( dy, h );
249 
250  if( newsize < 0 )
251  {
252  errno = ENOMEM;
253  goto error;
254  }
255 
256  if( newsize == 0 )
257  {
258  newsize = 1; /* make sure realloc() doesn't return NULL */
259  }
260 
261  newmap = (potrace_word*) realloc( bm->map, newsize );
262 
263  if( newmap == NULL )
264  {
265  goto error;
266  }
267 
268  bm->map = newmap;
269  bm->h = h;
270 
271  if( dy < 0 )
272  {
273  bm_flip( bm );
274  }
275 
276  return 0;
277 
278 error:
279 
280  if( dy < 0 )
281  {
282  bm_flip( bm );
283  }
284 
285  return 1;
286 }
287 
288 
289 #endif /* BITMAP_H */
static void bm_flip(potrace_bitmap_t *bm)
Definition: bitmap.h:217
static void bm_free(potrace_bitmap_t *bm)
Definition: bitmap.h:102
#define BM_WORDSIZE
Definition: bitmap.h:24
static potrace_bitmap_t * bm_dup(const potrace_bitmap_t *bm)
Definition: bitmap.h:170
potrace_word * map
Definition: potracelib.h:63
unsigned long potrace_word
Definition: potracelib.h:53
static potrace_word * bm_base(const potrace_bitmap_t *bm)
Definition: bitmap.h:86
#define bm_scanline(bm, y)
Definition: bitmap.h:32
static potrace_bitmap_t * bm_new(int w, int h)
Definition: bitmap.h:115
static int bm_resize(potrace_bitmap_t *bm, int h)
Definition: bitmap.h:237
static void bm_clear(potrace_bitmap_t *bm, int c)
Definition: bitmap.h:158
static void bm_invert(potrace_bitmap_t *bm)
Definition: bitmap.h:191
static ptrdiff_t bm_size(const potrace_bitmap_t *bm)
Definition: bitmap.h:76
size_t i
Definition: json11.cpp:597
#define BM_WORDBITS
Definition: bitmap.h:25
static ptrdiff_t getsize(int dy, int h)
Definition: bitmap.h:51
#define BM_ALLBITS
Definition: bitmap.h:27