Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 350 lines (283 sloc) 7.512 kb
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
1 #include <stdlib.h>
2 #include <stdio.h>
3589189 - fix a few compiler warnings
Tony Cook authored
3 #include <string.h>
e310e5f - more memory allocation integer overflow auditing
Tony Cook authored
4 #include "imager.h"
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
5
6 /*
7 2d bitmask with test and set operations
8 */
9
10 struct i_bitmap*
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
11 btm_new(i_img_dim xsize,i_img_dim ysize) {
12 size_t bytes;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
13 struct i_bitmap *btm;
f0960b1 - added integer overflow checks to many memory allocation calls
Tony Cook authored
14 btm=(struct i_bitmap*)mymalloc(sizeof(struct i_bitmap)); /* checked 4jul05 tonyc */
15 bytes = (xsize*ysize+8)/8;
16 if (bytes * 8 / ysize < xsize-1) { /* this is kind of rough */
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
17 fprintf(stderr, "Integer overflow allocating bitmap (" i_DFp ")",
18 i_DFcp(xsize, ysize));
f0960b1 - added integer overflow checks to many memory allocation calls
Tony Cook authored
19 exit(3);
20 }
21 btm->data=(char*)mymalloc(bytes); /* checked 4jul05 tonyc */
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
22 btm->xsize=xsize;
23 btm->ysize=ysize;
b934971 @tonycoz [rt #68994] initialize the btm data structure more efficiently
authored
24 memset(btm->data, 0, bytes);
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
25 return btm;
26 }
27
28
29 void
30 btm_destroy(struct i_bitmap *btm) {
31 myfree(btm->data);
32 myfree(btm);
33 }
34
35
36 int
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
37 btm_test(struct i_bitmap *btm,i_img_dim x,i_img_dim y) {
38 i_img_dim btno;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
39 if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) return 0;
40 btno=btm->xsize*y+x;
41 return (1<<(btno%8))&(btm->data[btno/8]);
42 }
43
44 void
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
45 btm_set(struct i_bitmap *btm,i_img_dim x,i_img_dim y) {
46 i_img_dim btno;
e25e59b Second attempt at flood fix.
Arnar Mar Hrafnkelsson authored
47 if (x<0 || x>btm->xsize-1 || y<0 || y>btm->ysize-1) abort();
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
48 btno=btm->xsize*y+x;
49 btm->data[btno/8]|=1<<(btno%8);
50 }
51
52
53
54
55
56 /*
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
57 Bucketed linked list - stack type
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
58 */
59
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
60 static struct llink *
61 llink_new(struct llink* p,size_t size);
62 static int
63 llist_llink_push(struct llist *lst, struct llink *lnk,const void *data);
64 static void
65 llink_destroy(struct llink* l);
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
66
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
67 /*
68 =item llist_new()
69 =synopsis struct llist *l = llist_new(100, sizeof(foo);
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
70
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
71 Create a new stack structure. Implemented as a linked list of pools.
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
72
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
73 Parameters:
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
74
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
75 =over
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
76
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
77 =item *
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
78
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
79 multip - number of entries in each pool
80
81 =item *
82
83 ssize - size of the objects being pushed/popped
84
85 =back
86
87 =cut
88 */
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
89
90 struct llist *
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
91 llist_new(int multip, size_t ssize) {
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
92 struct llist *l;
f0960b1 - added integer overflow checks to many memory allocation calls
Tony Cook authored
93 l = mymalloc(sizeof(struct llist)); /* checked 4jul05 tonyc */
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
94 l->h = NULL;
95 l->t = NULL;
96 l->multip = multip;
97 l->ssize = ssize;
98 l->count = 0;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
99 return l;
100 }
101
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
102 /*
103 =item llist_push()
104 =synopsis llist_push(l, &foo);
105
106 Push an item on the stack.
107
108 =cut
109 */
110
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
111 void
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
112 llist_push(struct llist *l,const void *data) {
113 size_t ssize = l->ssize;
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
114 int multip = l->multip;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
115
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
116 /* fprintf(stderr,"llist_push: data=0x%08X\n",data);
117 fprintf(stderr,"Chain size: %d\n", l->count); */
118
119 if (l->t == NULL) {
120 l->t = l->h = llink_new(NULL,ssize*multip); /* Tail is empty - list is empty */
121 /* fprintf(stderr,"Chain empty - extended\n"); */
122 }
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
123 else { /* Check for overflow in current tail */
124 if (l->t->fill >= l->multip) {
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
125 struct llink* nt = llink_new(l->t, ssize*multip);
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
126 l->t->n=nt;
127 l->t=nt;
128 /* fprintf(stderr,"Chain extended\n"); */
129 }
130 }
131 /* fprintf(stderr,"0x%08X\n",l->t); */
d03fd5a @tonycoz revert threading changes, they aren't ready for the mainline yet
authored
132 if (llist_llink_push(l,l->t,data)) {
133 i_fatal(3, "out of memory\n");
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
134 }
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
135 }
136
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
137 /*
138 =item llist_pop()
139
140 Pop an item off the list, storing it at C<data> which must have enough room for an object of the size supplied to llist_new().
141
142 returns 0 if the list is empty
143
144 =cut
145 */
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
146
147 int
148 llist_pop(struct llist *l,void *data) {
149 /* int ssize=l->ssize;
150 int multip=l->multip;*/
151 if (l->t == NULL) return 0;
152 l->t->fill--;
153 l->count--;
154 memcpy(data,(char*)(l->t->data)+l->ssize*l->t->fill,l->ssize);
155
156 if (!l->t->fill) { /* This link empty */
a73aeb5 Fixed most outstanding memory leaks that are revealed in the test cases.
Arnar Mar Hrafnkelsson authored
157 if (l->t->p == NULL) { /* and it's the only link */
158 llink_destroy(l->t);
159 l->h = l->t = NULL;
160 }
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
161 else {
162 l->t=l->t->p;
163 llink_destroy(l->t->n);
164 }
165 }
166 return 1;
167 }
168
169 void
170 llist_dump(struct llist *l) {
bc8930e avoid a dangerous cast (in an unused function)
Tony Cook authored
171 int j;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
172 int i=0;
173 struct llink *lnk;
174 lnk=l->h;
175 while(lnk != NULL) {
176 for(j=0;j<lnk->fill;j++) {
177 /* memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
bc8930e avoid a dangerous cast (in an unused function)
Tony Cook authored
178 /*memcpy(&k,(char*)(lnk->data)+l->ssize*j,sizeof(void*));*/
5e2762a can't add to a void *
Tony Cook authored
179 printf("%d - %p\n",i,*(void **)((char *)(lnk->data)+l->ssize*j));
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
180 i++;
181 }
182 lnk=lnk->n;
183 }
184 }
185
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
186 /*
187 =item llist_destroy()
188
189 Destroy a linked-list based stack.
190
191 =cut
192 */
193
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
194 void
195 llist_destroy(struct llist *l) {
196 struct llink *t,*lnk = l->h;
197 while( lnk != NULL ) {
198 t=lnk;
199 lnk=lnk->n;
200 myfree(t);
201 }
202 myfree(l);
203 }
204
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
205 /* Links */
206
207 static struct llink *
208 llink_new(struct llink* p,size_t size) {
209 struct llink *l;
210 l = mymalloc(sizeof(struct llink)); /* checked 4jul05 tonyc */
211 l->n = NULL;
212 l->p = p;
213 l->fill = 0;
214 l->data = mymalloc(size); /* checked 4jul05 tonyc - depends on caller to llist_push */
215 return l;
216 }
217
218 /* free's the data pointer, itself, and sets the previous' next pointer to null */
219
220 static void
221 llink_destroy(struct llink* l) {
222 if (l->p != NULL) { l->p->n=NULL; }
223 myfree(l->data);
224 myfree(l);
225 }
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
226
227
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
228 /* if it returns true there wasn't room for the
229 item on the link */
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
230
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
231 static int
232 llist_llink_push(struct llist *lst, struct llink *lnk, const void *data) {
233 int multip;
234 multip = lst->multip;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
235
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
236 /* fprintf(stderr,"llist_llink_push: data=0x%08X -> 0x%08X\n",data,*(int*)data);
237 fprintf(stderr,"ssize = %d, multip = %d, fill = %d\n",lst->ssize,lst->multip,lnk->fill); */
238 if (lnk->fill == lst->multip) return 1;
239 /* memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize); */
240 memcpy((char*)(lnk->data)+lnk->fill*lst->ssize,data,lst->ssize);
241
242 /* printf("data=%X res=%X\n",*(int*)data,*(int*)(lnk->data));*/
243 lnk->fill++;
244 lst->count++;
245 return 0;
246 }
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
247
248 /*
249 Oct-tree implementation
250 */
251
252 struct octt *
253 octt_new() {
254 int i;
255 struct octt *t;
256
f0960b1 - added integer overflow checks to many memory allocation calls
Tony Cook authored
257 t=(struct octt*)mymalloc(sizeof(struct octt)); /* checked 4jul05 tonyc */
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
258 for(i=0;i<8;i++) t->t[i]=NULL;
259 t->cnt=0;
260 return t;
261 }
262
263
264 /* returns 1 if the colors wasn't in the octtree already */
265
266
267 int
268 octt_add(struct octt *ct,unsigned char r,unsigned char g,unsigned char b) {
269 struct octt *c;
270 int i,cm;
fe622da Gabriel Vasseur's patch, corrected just enough for it to compile.
Tony Cook authored
271 int ci;
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
272 int rc;
273 rc=0;
274 c=ct;
275 /* printf("[r,g,b]=[%d,%d,%d]\n",r,g,b); */
276 for(i=7;i>-1;i--) {
277 cm=1<<i;
278 ci=((!!(r&cm))<<2)+((!!(g&cm))<<1)+!!(b&cm);
279 /* printf("idx[%d]=%d\n",i,ci); */
fe622da Gabriel Vasseur's patch, corrected just enough for it to compile.
Tony Cook authored
280 if (c->t[ci] == NULL) {
281 c->t[ci]=octt_new();
282 rc=1;
283 }
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
284 c=c->t[ci];
285 }
fe622da Gabriel Vasseur's patch, corrected just enough for it to compile.
Tony Cook authored
286 c->cnt++; /* New. The only thing really needed (I think) */
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
287 return rc;
288 }
289
290
291 void
292 octt_delete(struct octt *ct) {
293 int i;
294 for(i=0;i<8;i++) if (ct->t[i] != NULL) octt_delete(ct->t[i]); /* do not free instance here because it will free itself */
295 myfree(ct);
296 }
297
298
299 void
300 octt_dump(struct octt *ct) {
301 int i;
302 /* printf("node [0x%08X] -> (%d)\n",ct,ct->cnt); */
8a2cd31 - prevent a cast to integer warning on x64 builds in datatypes.c
Tony Cook authored
303 for(i=0;i<8;i++)
304 if (ct->t[i] != NULL)
305 printf("[ %d ] -> %p\n", i, (void *)ct->t[i]);
306 for(i=0;i<8;i++)
307 if (ct->t[i] != NULL)
308 octt_dump(ct->t[i]);
02d1d62 Initial revision
Arnar Mar Hrafnkelsson authored
309 }
310
311 /* note that all calls of octt_count are operating on the same overflow
312 variable so all calls will know at the same time if an overflow
313 has occured and stops there. */
314
315 void
316 octt_count(struct octt *ct,int *tot,int max,int *overflow) {
317 int i,c;
318 c=0;
319 if (!(*overflow)) return;
320 for(i=0;i<8;i++) if (ct->t[i]!=NULL) {
321 octt_count(ct->t[i],tot,max,overflow);
322 c++;
323 }
324 if (!c) (*tot)++;
325 if ( (*tot) > (*overflow) ) *overflow=0;
326 }
fe622da Gabriel Vasseur's patch, corrected just enough for it to compile.
Tony Cook authored
327
328 /* This whole function is new */
329 /* walk through the tree and for each colour, store its seen count in the
330 space pointed by *col_usage_it_adr */
331 void
332 octt_histo(struct octt *ct, unsigned int **col_usage_it_adr) {
333 int i,c;
334 c = 0;
335 for(i = 0; i < 8; i++)
336 if (ct->t[i] != NULL) {
337 octt_histo(ct->t[i], col_usage_it_adr);
338 c++;
339 }
340 if (!c) {
341 *(*col_usage_it_adr)++ = ct->cnt;
342 }
343 }
344
345
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
346 i_img_dim
347 i_abs(i_img_dim x) {
348 return x < 0 ? -x : x;
349 }
Something went wrong with that request. Please try again.