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