1 // cl_make_heap_GV_I().
7 #include "cln/GV_integer.h"
14 #include "cln/exception.h"
15 #include "cl_offsetof.h"
19 // Memory-efficient integer vectors: If all entries are known in advance to
20 // be >= 0 and < 2^m, we reserve only m bits for each entry. (m=1,2,4,8,16,32).
21 // Thus we end up with 6 kinds of bit/byte vectors, and the general integer
23 // For enquiring purposes, we store m in the vectorops table. Because of this,
24 // treating a cl_GV_RA as cl_GV_I is wrong. In particular, we cannot use the
25 // cl_null_GV_N to initialize a cl_GV_I; need a special cl_null_GV_I.
28 static void cl_gvector_integer_destructor (cl_heap* pointer)
30 #if (defined(__mips__) || defined(__mips64__)) && !defined(__GNUC__) // workaround SGI CC bug
31 (*(cl_heap_GV_I*)pointer).~cl_heap_GV();
33 (*(cl_heap_GV_I*)pointer).~cl_heap_GV_I();
37 // XXX: Ugh, this needs to be non-const (and non-static) for overriding
38 // the printing function (see cl_GV_I_debug.cc)
39 cl_class& cl_class_gvector_integer()
41 static cl_class instance = {
42 cl_gvector_integer_destructor,
48 static inline cl_heap_GV_I * outcast (cl_GV_inner<cl_I>* vec)
50 return (cl_heap_GV_I *)((char *) vec - offsetof(cl_heap_GV_I,v));
52 static inline const cl_heap_GV_I * outcast (const cl_GV_inner<cl_I>* vec)
54 return (const cl_heap_GV_I *)((const char *) vec - offsetof(cl_heap_GV_I,v));
58 // Add more info to the vectorops tables.
60 struct cl_GV_I_vectorops {
61 cl_GV_vectorops<cl_I> ops;
62 sintC m; // for maxbits
65 static inline cl_GV_I_vectorops* outcast (cl_GV_vectorops<cl_I>* vectorops)
67 return (cl_GV_I_vectorops*)((char *) vectorops - offsetof(cl_GV_I_vectorops,ops));
71 // Vectors of general integers.
73 struct cl_heap_GV_I_general : public cl_heap_GV_I {
75 // Standard allocation disabled.
76 void* operator new (size_t size) { unused size; throw runtime_exception(); }
77 // Standard deallocation disabled.
78 void operator delete (void* ptr) { unused ptr; throw runtime_exception(); }
79 // No default constructor.
80 cl_heap_GV_I_general ();
83 static const cl_I general_element (const cl_GV_inner<cl_I>* vec, uintC index)
85 return ((const cl_heap_GV_I_general *) outcast(vec))->data[index];
88 static void general_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
90 ((cl_heap_GV_I_general *) outcast(vec))->data[index] = x;
93 static void general_do_delete (cl_GV_inner<cl_I>* vec)
95 var cl_heap_GV_I_general* hv = (cl_heap_GV_I_general *) outcast(vec);
96 var uintC len = hv->v.length();
97 for (var uintC i = 0; i < len; i++)
101 static void general_copy_elements (const cl_GV_inner<cl_I>* srcvec, uintC srcindex, cl_GV_inner<cl_I>* destvec, uintC destindex, uintC count)
104 var const cl_heap_GV_I_general* srcv =
105 (const cl_heap_GV_I_general *) outcast(srcvec);
106 var cl_heap_GV_I_general* destv =
107 (cl_heap_GV_I_general *) outcast(destvec);
108 var uintC srclen = srcv->v.length();
109 var uintC destlen = destv->v.length();
110 if (!(srcindex <= srcindex+count && srcindex+count <= srclen))
111 throw runtime_exception();
112 if (!(destindex <= destindex+count && destindex+count <= destlen))
113 throw runtime_exception();
115 destv->data[destindex++] = srcv->data[srcindex++];
116 } while (--count > 0);
120 static cl_GV_I_vectorops general_vectorops = {{
124 general_copy_elements },
128 cl_heap_GV_I* cl_make_heap_GV_I (uintC len)
130 var cl_heap_GV_I_general* hv = (cl_heap_GV_I_general*) malloc_hook(offsetofa(cl_heap_GV_I_general,data)+sizeof(cl_I)*len);
132 hv->type = &cl_class_gvector_integer();
133 new (&hv->v) cl_GV_inner<cl_I> (len,&general_vectorops.ops);
134 for (var uintC i = 0; i < len; i++)
135 init1(cl_I, hv->data[i]) ();
140 // Vectors of integers requiring only few bits.
142 #define DEFINE_cl_heap_GV_I_bits(m,uint_t) \
143 struct cl_heap_GV_I_bits##m : public cl_heap_GV_I { \
145 /* Standard allocation disabled. */ \
146 void* operator new (size_t size) { unused size; throw runtime_exception(); } \
147 /* Standard deallocation disabled. */ \
148 void operator delete (void* ptr) { unused ptr; throw runtime_exception(); } \
149 /* No default constructor. */ \
150 cl_heap_GV_I_bits##m (); \
152 static const cl_I bits##m##_element (const cl_GV_inner<cl_I>* vec, uintC index); \
153 static void bits##m##_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x); \
154 static void bits##m##_copy_elements (const cl_GV_inner<cl_I>* srcvec, uintC srcindex, cl_GV_inner<cl_I>* destvec, uintC destindex, uintC count) \
157 var const cl_heap_GV_I_bits##m * srcv = \
158 (const cl_heap_GV_I_bits##m *) outcast(srcvec); \
159 var cl_heap_GV_I_bits##m * destv = \
160 (cl_heap_GV_I_bits##m *) outcast(destvec); \
161 var uintC srclen = srcv->v.length(); \
162 var uintC destlen = destv->v.length(); \
163 if (!(srcindex <= srcindex+count && srcindex+count <= srclen)) \
164 throw runtime_exception(); \
165 if (!(destindex <= destindex+count && destindex+count <= destlen)) \
166 throw runtime_exception(); \
167 if (m == intDsize) { \
168 var const uintD* srcptr = &srcv->data[srcindex]; \
169 var uintD* destptr = &destv->data[destindex]; \
171 *destptr++ = *srcptr++; \
172 } while (--count > 0); \
174 bits_copy(srcv->data,m*srcindex,destv->data,m*destindex,m*count); \
177 static cl_GV_I_vectorops bits##m##_vectorops = {{ \
179 bits##m##_set_element, \
181 bits##m##_copy_elements }, \
185 static void bits_do_delete (cl_GV_inner<cl_I>* vec)
190 // Copy bits srcptr.bits[srcindex..srcindex+count-1] into destptr.bits[destindex..destindex+count-1].
191 // Assumes that all range checks have already been performed.
192 static void bits_copy (const uintD* srcptr, uintC srcindex, uintD* destptr, uintC destindex, uintC count)
194 srcptr += floor(srcindex,intDsize);
195 destptr += floor(destindex,intDsize);
196 srcindex = srcindex%intDsize;
197 destindex = destindex%intDsize;
198 // Now 0 <= srcindex < intDsize and 0 <= destindex < intDsize.
199 if (srcindex == destindex) {
200 // src and dest are aligned with respect to each other.
202 if (count <= intDsize-srcindex) {
203 *destptr ^= (*destptr ^ *srcptr) & ((uintD)(bit(count)-1) << srcindex);
206 *destptr ^= (*destptr ^ *srcptr) & (uintD)minus_bit(srcindex);
209 count -= intDsize-srcindex;
211 // Now srcindex and destindex can be assumed to be 0.
212 var uintC count1 = count%intDsize;
213 count = floor(count,intDsize);
216 *destptr++ = *srcptr++;
217 } while (--count > 0);
220 *destptr ^= (*destptr ^ *srcptr) & (uintD)(bit(count1)-1);
223 var uintC i = destindex - srcindex;
225 if (destindex >= srcindex) { // i > 0
226 if (count <= intDsize-destindex) {
227 *destptr ^= (*destptr ^ (*srcptr << i)) & ((uintD)(bit(count)-1) << destindex);
230 *destptr ^= (*destptr ^ (*srcptr << i)) & (uintD)minus_bit(destindex);
232 tmp = *srcptr >> (intDsize-i);
233 count -= intDsize-destindex;
235 if (count <= intDsize-srcindex) {
236 *destptr ^= (*destptr ^ (*srcptr >> -i)) & ((uintD)(bit(count)-1) << destindex);
239 tmp = (*destptr & (uintD)(bit(destindex)-1)) | ((*srcptr >> srcindex) << destindex);
244 // tmp now contains the low i bits to be put into *destptr.
245 var uintC count1 = count%intDsize;
246 count = floor(count,intDsize);
251 lastdest = shiftleftcopy_loop_up(srcptr,destptr,count,i);
254 // lastdest now contains the i bits shifted out of the top of the source.
258 lastdest |= *(srcptr += count) << i;
259 *destptr ^= (*destptr ^ lastdest) & (uintD)(bit(count1)-1);
265 // It would be most natural to use the following type for uint_t:
266 // m = 1: uint_t = uint8
267 // m = 2: uint_t = uint8
268 // m = 4: uint_t = uint8
269 // m = 8: uint_t = uint8
270 // m = 16: uint_t = uint16
271 // m = 32: uint_t = uint32
272 // But we want to have a fast copy_elements routine. And for m=1,
273 // we also want to use the fast shiftxor_loop_up() function for addition.
274 // Hence we use the uint_t = uintD in all cases. (NB: intDsize>=32.)
276 // The last ceiling(len*m/intDsize)*intDsize-len*m unused bits in the last word
277 // are always 0. This provides some simplification for routines which work on
278 // entire words: They don't need to special-case the last word.
281 DEFINE_cl_heap_GV_I_bits(1,uintD)
283 static const cl_I bits1_element (const cl_GV_inner<cl_I>* vec, uintC index)
285 return (unsigned int)((((const cl_heap_GV_I_bits1 *) outcast(vec))->data[index/intDsize] >> (index%intDsize)) & 0x1);
287 static void bits1_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
293 var uintD* ptr = &((cl_heap_GV_I_bits1 *) outcast(vec))->data[index/intDsize];
294 index = index%intDsize;
295 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0x1 << index));
299 throw runtime_exception();
303 DEFINE_cl_heap_GV_I_bits(2,uintD)
305 static const cl_I bits2_element (const cl_GV_inner<cl_I>* vec, uintC index)
307 return (unsigned int)((((const cl_heap_GV_I_bits2 *) outcast(vec))->data[index/(intDsize/2)] >> (2*(index%(intDsize/2)))) & 0x3);
309 static void bits2_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
315 var uintD* ptr = &((cl_heap_GV_I_bits2 *) outcast(vec))->data[index/(intDsize/2)];
316 index = 2*(index%(intDsize/2));
317 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0x3 << index));
321 throw runtime_exception();
325 DEFINE_cl_heap_GV_I_bits(4,uintD)
327 static const cl_I bits4_element (const cl_GV_inner<cl_I>* vec, uintC index)
329 return (unsigned int)((((const cl_heap_GV_I_bits4 *) outcast(vec))->data[index/(intDsize/4)] >> (4*(index%(intDsize/4)))) & 0xF);
331 static void bits4_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
337 var uintD* ptr = &((cl_heap_GV_I_bits4 *) outcast(vec))->data[index/(intDsize/4)];
338 index = 4*(index%(intDsize/4));
339 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xF << index));
343 throw runtime_exception();
347 DEFINE_cl_heap_GV_I_bits(8,uintD)
349 static const cl_I bits8_element (const cl_GV_inner<cl_I>* vec, uintC index)
351 #if CL_CPU_BIG_ENDIAN_P
352 return (unsigned int)((((const cl_heap_GV_I_bits8 *) outcast(vec))->data[index/(intDsize/8)] >> (8*(index%(intDsize/8)))) & 0xFF);
354 // Optimization which assumes little-endian storage of uint8 in an uintD
355 return (unsigned int)(((uint8*)(((const cl_heap_GV_I_bits8 *) outcast(vec))->data))[index]);
358 static void bits8_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
364 #if CL_CPU_BIG_ENDIAN_P
365 var uintD* ptr = &((cl_heap_GV_I_bits8 *) outcast(vec))->data[index/(intDsize/8)];
366 index = 8*(index%(intDsize/8));
367 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xFF << index));
369 // Optimization which assumes little-endian storage of uint8 in an uintD
370 ((uint8*)(((cl_heap_GV_I_bits8 *) outcast(vec))->data))[index] = xval;
375 throw runtime_exception();
379 DEFINE_cl_heap_GV_I_bits(16,uintD)
381 static const cl_I bits16_element (const cl_GV_inner<cl_I>* vec, uintC index)
383 #if CL_CPU_BIG_ENDIAN_P
384 return (unsigned int)((((const cl_heap_GV_I_bits16 *) outcast(vec))->data[index/(intDsize/16)] >> (16*(index%(intDsize/16)))) & 0xFFFF);
386 // Optimization which assumes little-endian storage of uint16 in an uintD
387 return (unsigned int)(((uint16*)(((const cl_heap_GV_I_bits16 *) outcast(vec))->data))[index]);
390 static void bits16_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
395 if (xval <= 0xFFFF) {
396 #if CL_CPU_BIG_ENDIAN_P
397 var uintD* ptr = &((cl_heap_GV_I_bits16 *) outcast(vec))->data[index/(intDsize/16)];
398 index = 16*(index%(intDsize/16));
399 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xFFFF << index));
401 // Optimization which assumes little-endian storage of uint16 in an uintD
402 ((uint16*)(((cl_heap_GV_I_bits16 *) outcast(vec))->data))[index] = xval;
407 throw runtime_exception();
411 DEFINE_cl_heap_GV_I_bits(32,uintD)
413 static const cl_I bits32_element (const cl_GV_inner<cl_I>* vec, uintC index)
416 return (unsigned long)(((const cl_heap_GV_I_bits32 *) outcast(vec))->data[index]);
417 #elif CL_CPU_BIG_ENDIAN_P
418 return (unsigned long)((((const cl_heap_GV_I_bits32 *) outcast(vec))->data[index/(intDsize/32)] >> (32*(index%(intDsize/32)))) & 0xFFFFFFFF);
420 // Optimization which assumes little-endian storage of uint32 in an uintD
421 return (unsigned long)(((uint32*)(((const cl_heap_GV_I_bits32 *) outcast(vec))->data))[index]);
424 static void bits32_set_element (cl_GV_inner<cl_I>* vec, uintC index, const cl_I& x)
426 var uint32 xval = cl_I_to_UL(x);
428 ((cl_heap_GV_I_bits32 *) outcast(vec))->data[index] = xval;
429 #elif CL_CPU_BIG_ENDIAN_P
430 var uintD* ptr = &((cl_heap_GV_I_bits32 *) outcast(vec))->data[index/(intDsize/32)];
431 index = 32*(index%(intDsize/32));
432 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xFFFFFFFF << index));
434 // Optimization which assumes little-endian storage of uint32 in an uintD
435 ((uint32*)(((cl_heap_GV_I_bits32 *) outcast(vec))->data))[index] = xval;
440 static cl_GV_I_vectorops* bits_vectorops[6] = {
449 cl_heap_GV_I* cl_make_heap_GV_I (uintC len, sintC m)
451 // Determine log2(bits).
455 log2_bits = 0; break;
457 log2_bits = 1; break;
459 log2_bits = 2; break;
460 case 5: case 6: case 7: case 8:
461 log2_bits = 3; break;
462 case 9: case 10: case 11: case 12:
463 case 13: case 14: case 15: case 16:
464 log2_bits = 4; break;
465 case 17: case 18: case 19: case 20:
466 case 21: case 22: case 23: case 24:
467 case 25: case 26: case 27: case 28:
468 case 29: case 30: case 31: case 32:
469 log2_bits = 5; break;
471 return cl_make_heap_GV_I(len);
473 // For room allocation purposes, be pessimistic: assume the uintD case (since intDsize>=32).
474 var uintC words = // ceiling(len*2^log2_bits,intDsize)
475 (((sintC)len-1)>>(log2_intDsize-log2_bits))+1;
476 var cl_heap_GV_I_bits32* hv = (cl_heap_GV_I_bits32*) malloc_hook(offsetofa(cl_heap_GV_I_bits32,data)+sizeof(uintD)*words);
478 hv->type = &cl_class_gvector_integer();
479 new (&hv->v) cl_GV_inner<cl_I> (len,&bits_vectorops[log2_bits]->ops);
480 var uintD* ptr = (uintD*)(hv->data);
481 for (var uintC i = 0; i < words; i++)
483 return (cl_heap_GV_I*) hv;
487 sintC cl_heap_GV_I::maxbits () const
489 return outcast(v.vectorops)->m;
494 const cl_GV_I cl_null_GV_I = cl_null_GV_I;
496 int cl_GV_I_init_helper::count = 0;
498 cl_GV_I_init_helper::cl_GV_I_init_helper()
501 new ((void *)&cl_null_GV_I) cl_GV_I((uintC)0);
504 cl_GV_I_init_helper::~cl_GV_I_init_helper()
507 // Nothing to clean up