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