GRASS GIS 8 Programmer's Manual 8.2.1RC1(2022)-exported
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
44static int Mode = BM_FLAT;
45static 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
60struct 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 */
93int 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
152int 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
190int 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
223int 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
248size_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
272int 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
316struct 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
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}
struct BM * BM_create(int x, int y)
Create bitmap of dimension x/y and return structure token.
Definition: bitmap.c:60
int BM_set(struct BM *map, int x, int y, int val)
Sets bitmap value to 'val' at location 'x' 'y'.
Definition: bitmap.c:190
int BM_file_write(FILE *fp, struct BM *map)
Write bitmap out to file.
Definition: bitmap.c:272
size_t BM_get_map_size(struct BM *map)
Returns size in bytes that bitmap is taking up.
Definition: bitmap.c:248
int BM_get(struct BM *map, int x, int y)
Gets 'val' from the bitmap.
Definition: bitmap.c:223
int BM_destroy(struct BM *map)
Destroy bitmap and free all associated memory.
Definition: bitmap.c:93
#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_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:152
#define BM_col_to_byte(x)
Definition: bitmap.c:41
#define NULL
Definition: ccmath.h:32
void link_set_chunk_size(int size)
Definition: linkm/init.c:30
struct link_head * link_init(int size)
Definition: linkm/init.c:40
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:44
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:366
int BM_get_sparse(struct BM *map, int x, int y)
Returns sparse bitmap value at location 'x'/'y'.
Definition: sparse.c:248
size_t BM_get_map_size_sparse(struct BM *map)
Returns size of sparse bitmap in bytes.
Definition: sparse.c:274
int BM_destroy_sparse(struct BM *map)
Destroy sparse bitmap and free all associated memory.
Definition: sparse.c:93
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:131
#define x