GRASS GIS 8 Programmer's Manual 8.4.1(2025)-45ca3179ab
Loading...
Searching...
No Matches
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
43static int Mode = BM_FLAT;
44static 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
58struct 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 */
89int 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
147int 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
185int 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
217int 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
241size_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
264int 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
306struct 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
371readsparse:
372
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
#define BM_col_to_bit(x)
Definition bitmap.c:41
struct BM * BM_file_read(FILE *fp)
Create map structure and load it from file.
Definition bitmap.c:306
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 NULL
Definition ccmath.h:32
void link_set_chunk_size(int size)
Definition linkm/init.c:32
struct link_head * link_init(int size)
Definition linkm/init.c:42
VOID_T * link_new(struct link_head *Head)
Definition new.c:12
struct BM * BM_create_sparse(int x, int y)
Create a sparse bitmap of dimension 'x'/'y'.
Definition sparse.c:42
int BM_file_write_sparse(FILE *fp, struct BM *map)
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 *map, int x, int y)
Returns sparse bitmap value at location 'x'/'y'.
Definition sparse.c:240
size_t BM_get_map_size_sparse(struct BM *map)
Returns size of sparse bitmap in bytes.
Definition sparse.c:265
int BM_destroy_sparse(struct BM *map)
Destroy sparse bitmap and free all associated memory.
Definition sparse.c:88
int BM_set_sparse(struct BM *map, int x, int y, int val)
Set sparse bitmap value to 'val' at location 'x'/'y'.
Definition sparse.c:125
#define x