GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
bitmap.c
Go to the documentation of this file.
1 /*
2  ** Bitmap library
3  **
4  ** Written by David Gerdes 12 November 1992
5  ** US Army Construction Engineering Research Laboratories
6  **
7  **
8  ** This library provides basic support for the creation and manipulation
9  ** of two dimensional bitmap arrays.
10  **
11  ** struct BM *
12  ** BM_create (x, y) Create bitmap of specified dimensions
13  **
14  ** BM_set_mode (mode, size) Specify Mode and data size in bits.
15  ** Affects all further calls to BM_create()
16  ** Mode can be BM_FLAT or BM_SPARSE
17  ** Size can only be 1 currently.
18  **
19  ** BM_destroy (map) Destroy bitmap and free memory
20  **
21  ** BM_set (map, x, y, val) Set array position to val [TRUE/FALSE]
22  **
23  ** BM_get (map, x, y) Return value at array position
24  **
25  **
26  ** BM_file_write (fp, map) Write bitmap to file
27  **
28  ** struct BM *
29  ** BM_file_read (fp) Create bitmap and load from file
30  **
31  ** BM_get_map_size (map) returns size in bytes that bitmap is
32  ** taking up. For diagnosis use.
33  */
34 
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <grass/linkm.h>
38 #include <grass/bitmap.h>
39 
40 
41 #define BM_col_to_byte(x) ((x) >> 3) /* x / 8 */
42 #define BM_col_to_bit(x) ((x) & 7) /* x % 8 */
43 
44 static int Mode = BM_FLAT;
45 static int Size = 1;
46 
47 
48 /*!
49  * \brief Create bitmap of dimension x/y and return structure token.
50  *
51  * Bitmap is initialized to all zeros
52  *
53  * \param x x dimension
54  * \param y y dimension
55  *
56  * \return pointer to struct BM
57  * \return NULL on error
58  */
59 
60 struct BM *BM_create(int x, int y)
61 {
62  struct BM *map;
63 
64  if (Mode == BM_SPARSE)
65  return BM_create_sparse(x, y);
66 
67  if (NULL == (map = (struct BM *)malloc(sizeof(struct BM))))
68  return (NULL);
69 
70  map->bytes = (x + 7) / 8;
71 
72  if (NULL ==
73  (map->data = (unsigned char *)calloc(map->bytes * y, sizeof(char))))
74  return (NULL);
75 
76  map->rows = y;
77  map->cols = x;
78  map->sparse = 0;
79 
80  return map;
81 }
82 
83 
84 /*!
85  * \brief Destroy bitmap and free all associated memory
86  *
87  * \param map
88  * \return int returns 0
89  */
90 int BM_destroy(struct BM *map)
91 {
92  if (map->sparse)
93  return BM_destroy_sparse(map);
94 
95  free(map->data);
96  free(map);
97 
98  return 0;
99 }
100 
101 
102 /*
103  ** Caller can specify type of data structure to use for bitmap, as
104  ** well as the size of the data values. Currently since this is
105  ** the 'bitmap' library, size can ONLY have value 1.
106  ** Size is number of bits of storage per cell.
107  **
108  ** Mode:
109  ** BM_FLAT Your basic packed bitmap, eight values are stored per byte
110  ** Thus you get a 1:8 compression over using char arrays
111  ** and a 1:32 compression over using CELL arrays.
112  **
113  **
114  ** BM_SPARSE Linked array of values. Much more efficient for large
115  ** very sparse arrays. Slower access, especially for writing,
116  ** but can save several orders of magnitude of memory on large
117  ** bitmaps since size of FLAT bitmap is O(M*N)
118  **
119  **
120  ** Returns 0 or negative on error;
121  ** If error it will print a warning message to stderr and continue
122  ** continue by running but will not change the option in error.
123  */
124 
125 /*!
126  * \brief
127  *
128  * Specify the type of data structure to use for bitmap.
129  * 'mode' can be either BM_FLAT or BM_SPARSE:
130  *
131  * BM_FLAT is a basic packed bitmap - eight values stored per byte
132  * thus creating a 1:8 compression over using char arrays and a
133  * 1:32 compression over using CELL arrays.
134  *
135  * BM_SPARSE is a linked array of values. This is much more efficient
136  * for large, very sparse arrays. It is slower to access, especially
137  * for writing, but can save several orders of magnitude of memory on
138  * large bitmaps.
139  *
140  * NOTE: At this time 'size' must be passed a value of 1
141  *
142  * returns 0 on success or -1 on error
143  *
144  * \param mode
145  * \param size
146  * \return int
147  */
148 
149 int BM_set_mode(int mode, int size)
150 {
151  int ret = 0;
152 
153  switch (mode) {
154  case BM_FLAT:
155  case BM_SPARSE:
156  Mode = mode;
157  default:
158  fprintf(stderr, "BM_set_mode: Unknown mode: %d\n", mode);
159  ret--;
160  }
161 
162  if (size != 1) {
163  fprintf(stderr, "BM_set_mode: Bad size: %d\n", size);
164  ret--;
165  }
166  else
167  Size = size;
168 
169  return ret;
170 }
171 
172 
173 /*!
174  * \brief
175  *
176  * Sets bitmap value to 'val' at location 'x' 'y'
177  *
178  * Returns 0 on success
179  *
180  * \param map
181  * \param x
182  * \param y
183  * \param val
184  * \return int
185  */
186 
187 int BM_set(struct BM *map, int x, int y, int val)
188 {
189  unsigned char byte;
190 
191  if (x < 0 || x >= map->cols || y < 0 || y >= map->rows)
192  return 0;
193 
194  if (map->sparse)
195  return BM_set_sparse(map, x, y, val);
196 
197  byte = 0x01 << BM_col_to_bit(x);
198  if (val)
199  map->data[BM_col_to_byte(x) + y * map->bytes] |= byte;
200  else
201  map->data[BM_col_to_byte(x) + y * map->bytes] &= ~byte;
202 
203  return 0;
204 }
205 
206 
207 /*!
208  * \brief
209  *
210  * Gets 'val' from the bitmap
211  *
212  * Returns 0 or 1 on success or -1 on error
213  *
214  * \param map
215  * \param x
216  * \param y
217  * \return int
218  */
219 
220 int BM_get(struct BM *map, int x, int y)
221 {
222  unsigned char byte;
223 
224  if (x < 0 || x >= map->cols || y < 0 || y >= map->rows)
225  return -1;
226 
227  if (map->sparse)
228  return BM_get_sparse(map, x, y);
229 
230  byte = map->data[BM_col_to_byte(x) + y * map->bytes];
231 
232  return byte >> BM_col_to_bit(x) & 0x01;
233 }
234 
235 
236 /*!
237  * \brief
238  *
239  * Returns size in bytes that bitmap is taking up.
240  *
241  * \param map
242  * \return int
243  */
244 
245 size_t BM_get_map_size(struct BM *map)
246 {
247  if (map->sparse)
248  return BM_get_map_size_sparse(map);
249 
250  return (size_t) map->bytes * map->rows;
251 }
252 
253 
254 /*!
255  * \brief
256  *
257  * Write bitmap out to file
258  *
259  * Expects open file pointer 'fp' and existing map structure.
260  * Caller is responsible to open and close 'fp'.
261  *
262  * Returns 0 or -1 on error
263  *
264  * \param fp
265  * \param map
266  * \return int
267  */
268 
269 int BM_file_write(FILE * fp, struct BM *map)
270 {
271  char c;
272  int i;
273 
274  if (map->sparse)
275  return BM_file_write_sparse(fp, map);
276 
277  c = BM_MAGIC;
278  fwrite(&c, sizeof(char), sizeof(char), fp);
279 
280  fwrite(BM_TEXT, BM_TEXT_LEN, sizeof(char), fp);
281 
282  c = BM_FLAT;
283  fwrite(&c, sizeof(char), sizeof(char), fp);
284 
285  fwrite(&(map->rows), sizeof(map->rows), sizeof(char), fp);
286 
287  fwrite(&(map->cols), sizeof(map->cols), sizeof(char), fp);
288 
289  for (i = 0; i < map->rows; i++)
290  if (map->bytes !=
291  fwrite(&(map->data[i * map->bytes]), sizeof(char), map->bytes,
292  fp))
293  return -1;
294  fflush(fp);
295 
296  return 0;
297 }
298 
299 
300 /*!
301  * \brief
302  *
303  * Create map structure and load it from file
304  *
305  * 'fp' should previously been created by <b>BM_file_write()</b>
306  *
307  * Returns struct BM * or NULL on error
308  *
309  * \param fp
310  * \return struct BM
311  */
312 
313 struct BM *BM_file_read(FILE * fp)
314 {
315  struct BM *map;
316  char c;
317  char buf[BM_TEXT_LEN + 1];
318  int i, y, n;
319  struct BMlink *p = NULL, *p2;
320  int cnt;
321 
322  if (NULL == (map = (struct BM *)malloc(sizeof(struct BM))))
323  return (NULL);
324 
325  fread(&c, sizeof(char), sizeof(char), fp);
326  if (c != BM_MAGIC)
327  return NULL;
328 
329  fread(buf, BM_TEXT_LEN, sizeof(char), fp);
330 
331  fread(&c, sizeof(char), sizeof(char), fp);
332  map->sparse = c;
333 
334 
335  fread(&(map->rows), sizeof(map->rows), sizeof(char), fp);
336 
337  fread(&(map->cols), sizeof(map->cols), sizeof(char), fp);
338 
339  map->bytes = (map->cols + 7) / 8;
340 
341  if (map->sparse == BM_SPARSE)
342  goto readsparse;
343 
344  if (NULL == (map->data = (unsigned char *)malloc(map->bytes * map->rows)))
345  return (NULL);
346 
347 
348  for (i = 0; i < map->rows; i++)
349  if (map->bytes !=
350  fread(&(map->data[i * map->bytes]), sizeof(char), map->bytes, fp))
351  return NULL;
352 
353 
354  return map;
355 
356  readsparse:
357 
358  link_set_chunk_size(500);
359  map->token = link_init(sizeof(struct BMlink));
360 
361 
362  if (NULL == (map->data = (unsigned char *)
363  malloc(sizeof(struct BMlink *) * map->rows)))
364  return (NULL);
365 
366  for (y = 0; y < map->rows; y++) {
367  /* first get number of links */
368  fread(&i, sizeof(i), sizeof(char), fp);
369  cnt = i;
370 
371 
372  /* then read them in */
373  for (i = 0; i < cnt; i++) {
374  p2 = (struct BMlink *)link_new(map->token);
375 
376  if (i == 0) {
377  ((struct BMlink **)(map->data))[y] = p2;
378  p = p2;
379  }
380  else {
381  p->next = p2;
382  p = p2;
383  }
384 
385  fread(&n, sizeof(n), sizeof(char), fp);
386  p->count = n;
387 
388  fread(&n, sizeof(n), sizeof(char), fp);
389  p->val = n;
390  p->next = NULL;
391  }
392  }
393 
394  return map;
395 }
int BM_get(struct BM *map, int x, int y)
Gets &#39;val&#39; from the bitmap.
Definition: bitmap.c:220
void link_set_chunk_size(int)
Definition: linkm/init.c:30
Definition: bitmap.h:17
int rows
Definition: bitmap.h:19
int BM_file_write(FILE *fp, struct BM *map)
Write bitmap out to file.
Definition: bitmap.c:269
unsigned char * data
Definition: bitmap.h:22
void free(void *)
#define NULL
Definition: ccmath.h:32
#define x
int BM_destroy(struct BM *map)
Destroy bitmap and free all associated memory.
Definition: bitmap.c:90
int sparse
Definition: bitmap.h:23
int BM_set_sparse(struct BM *, int, int, int)
Set sparse bitmap value to &#39;val&#39; at location &#39;x&#39;/&#39;y&#39;.
Definition: sparse.c:128
void * malloc(YYSIZE_T)
VOID_T * link_new(struct link_head *)
Definition: new.c:12
#define BM_SPARSE
Definition: bitmap.h:11
#define BM_MAGIC
Definition: bitmap.h:4
int BM_destroy_sparse(struct BM *)
Destroy sparse bitmap and free all associated memory.
Definition: sparse.c:90
#define BM_TEXT_LEN
Definition: bitmap.h:7
#define BM_col_to_bit(x)
Definition: bitmap.c:42
struct BM * BM_file_read(FILE *fp)
Create map structure and load it from file.
Definition: bitmap.c:313
int BM_file_write_sparse(FILE *, struct BM *)
Write sparse bitmap matrix out to disk file &#39;fp&#39;. NOTE: &#39;fp&#39; must already be opened and later closed ...
Definition: sparse.c:364
#define BM_FLAT
Definition: bitmap.h:9
struct BM * BM_create(int x, int y)
Create bitmap of dimension x/y and return structure token.
Definition: bitmap.c:60
#define BM_col_to_byte(x)
Definition: bitmap.c:41
struct link_head * link_init(int)
Definition: linkm/init.c:40
size_t BM_get_map_size(struct BM *map)
Returns size in bytes that bitmap is taking up.
Definition: bitmap.c:245
size_t bytes
Definition: bitmap.h:21
int cols
Definition: bitmap.h:20
struct BM * BM_create_sparse(int, int)
Create a sparse bitmap of dimension &#39;x&#39;/&#39;y&#39;.
Definition: sparse.c:44
int BM_get_sparse(struct BM *, int, int)
Returns sparse bitmap value at location &#39;x&#39;/&#39;y&#39;.
Definition: sparse.c:246
size_t BM_get_map_size_sparse(struct BM *)
Returns size of sparse bitmap in bytes.
Definition: sparse.c:272
int BM_set_mode(int mode, int size)
Specify the type of data structure to use for bitmap. &#39;mode&#39; can be either BM_FLAT or BM_SPARSE: ...
Definition: bitmap.c:149
int BM_set(struct BM *map, int x, int y, int val)
Sets bitmap value to &#39;val&#39; at location &#39;x&#39; &#39;y&#39;.
Definition: bitmap.c:187
struct link_head * token
Definition: bitmap.h:25
#define BM_TEXT
Definition: bitmap.h:6