1 // cl_make_heap_GV_I().
4 #include "base/cl_sysdep.h"
7 #include "cln/GV_integer.h"
12 #include "integer/cl_I.h"
13 #include "base/digitseq/cl_DS.h"
14 #include "cln/exception.h"
15 #include "base/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 (*(cl_heap_GV_I*)pointer).~cl_heap_GV_I();
33 // XXX: Ugh, this needs to be non-const (and non-static) for overriding
34 // the printing function (see cl_GV_I_debug.cc)
35 cl_class& cl_class_gvector_integer()
37 static cl_class instance = {
38 cl_gvector_integer_destructor,
44 static inline cl_heap_GV_I * outcast (cl_GV_inner<cl_I>* vec)
46 return (cl_heap_GV_I *)((char *) vec - offsetof(cl_heap_GV_I,v));
48 static inline const cl_heap_GV_I * outcast (const cl_GV_inner<cl_I>* vec)
50 return (const cl_heap_GV_I *)((const char *) vec - offsetof(cl_heap_GV_I,v));
54 // Add more info to the vectorops tables.
56 struct cl_GV_I_vectorops {
57 cl_GV_vectorops<cl_I> ops;
58 sintC m; // for maxbits
61 static inline cl_GV_I_vectorops* outcast (cl_GV_vectorops<cl_I>* vectorops)
63 return (cl_GV_I_vectorops*)((char *) vectorops - offsetof(cl_GV_I_vectorops,ops));
67 // Vectors of general integers.
69 struct cl_heap_GV_I_general : public cl_heap_GV_I {
71 // Standard allocation disabled.
72 void* operator new (size_t size) = delete;
73 // Standard deallocation disabled.
74 void operator delete (void* ptr) = delete;
75 // No default constructor.
76 cl_heap_GV_I_general ();
79 static const cl_I general_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
81 return ((const cl_heap_GV_I_general *) outcast(vec))->data[index];
84 static void general_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
86 ((cl_heap_GV_I_general *) outcast(vec))->data[index] = x;
89 static void general_do_delete (cl_GV_inner<cl_I>* vec)
91 cl_heap_GV_I_general* hv = (cl_heap_GV_I_general *) outcast(vec);
92 std::size_t len = hv->v.size();
93 for (std::size_t i = 0; i < len; i++)
97 static void general_copy_elements (const cl_GV_inner<cl_I>* srcvec, std::size_t srcindex, cl_GV_inner<cl_I>* destvec, std::size_t destindex, std::size_t count)
100 const cl_heap_GV_I_general* srcv =
101 (const cl_heap_GV_I_general *) outcast(srcvec);
102 cl_heap_GV_I_general* destv =
103 (cl_heap_GV_I_general *) outcast(destvec);
104 std::size_t srclen = srcv->v.size();
105 std::size_t destlen = destv->v.size();
106 if (!(srcindex <= srcindex+count && srcindex+count <= srclen))
107 throw runtime_exception();
108 if (!(destindex <= destindex+count && destindex+count <= destlen))
109 throw runtime_exception();
111 destv->data[destindex++] = srcv->data[srcindex++];
112 } while (--count > 0);
116 static cl_GV_I_vectorops general_vectorops = {{
120 general_copy_elements },
124 cl_heap_GV_I* cl_make_heap_GV_I (std::size_t len)
126 cl_heap_GV_I_general* hv = (cl_heap_GV_I_general*) malloc_hook(offsetofa(cl_heap_GV_I_general,data)+sizeof(cl_I)*len);
128 hv->type = &cl_class_gvector_integer();
129 new (&hv->v) cl_GV_inner<cl_I> (len,&general_vectorops.ops);
130 for (std::size_t i = 0; i < len; i++)
131 init1(cl_I, hv->data[i]) ();
136 // Vectors of integers requiring only few bits.
138 #define DEFINE_cl_heap_GV_I_bits(m,uint_t) \
139 struct cl_heap_GV_I_bits##m : public cl_heap_GV_I { \
141 /* Standard allocation disabled. */ \
142 void* operator new (size_t size) = delete; \
143 /* Standard deallocation disabled. */ \
144 void operator delete (void* ptr) = delete; \
145 /* No default constructor. */ \
146 cl_heap_GV_I_bits##m (); \
148 static const cl_I bits##m##_element (const cl_GV_inner<cl_I>* vec, std::size_t index); \
149 static void bits##m##_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x); \
150 static void bits##m##_copy_elements (const cl_GV_inner<cl_I>* srcvec, std::size_t srcindex, cl_GV_inner<cl_I>* destvec, std::size_t destindex, std::size_t count) \
153 const cl_heap_GV_I_bits##m * srcv = \
154 (const cl_heap_GV_I_bits##m *) outcast(srcvec); \
155 cl_heap_GV_I_bits##m * destv = \
156 (cl_heap_GV_I_bits##m *) outcast(destvec); \
157 std::size_t srclen = srcv->v.size(); \
158 std::size_t destlen = destv->v.size(); \
159 if (!(srcindex <= srcindex+count && srcindex+count <= srclen)) \
160 throw runtime_exception(); \
161 if (!(destindex <= destindex+count && destindex+count <= destlen)) \
162 throw runtime_exception(); \
163 if (m == intDsize) { \
164 const uintD* srcptr = &srcv->data[srcindex]; \
165 uintD* destptr = &destv->data[destindex]; \
167 *destptr++ = *srcptr++; \
168 } while (--count > 0); \
170 bits_copy(srcv->data,m*srcindex,destv->data,m*destindex,m*count); \
173 static cl_GV_I_vectorops bits##m##_vectorops = {{ \
175 bits##m##_set_element, \
177 bits##m##_copy_elements }, \
181 static void bits_do_delete (cl_GV_inner<cl_I>* vec)
186 // Copy bits srcptr.bits[srcindex..srcindex+count-1] into destptr.bits[destindex..destindex+count-1].
187 // Assumes that all range checks have already been performed.
188 static void bits_copy (const uintD* srcptr, std::size_t srcindex, uintD* destptr, std::size_t destindex, std::size_t count)
190 srcptr += floor(srcindex,intDsize);
191 destptr += floor(destindex,intDsize);
192 srcindex = srcindex%intDsize;
193 destindex = destindex%intDsize;
194 // Now 0 <= srcindex < intDsize and 0 <= destindex < intDsize.
195 if (srcindex == destindex) {
196 // src and dest are aligned with respect to each other.
198 if (count <= intDsize-srcindex) {
199 *destptr ^= (*destptr ^ *srcptr) & ((uintD)(bit(count)-1) << srcindex);
202 *destptr ^= (*destptr ^ *srcptr) & (uintD)minus_bit(srcindex);
205 count -= intDsize-srcindex;
207 // Now srcindex and destindex can be assumed to be 0.
208 std::size_t count1 = count%intDsize;
209 count = floor(count,intDsize);
212 *destptr++ = *srcptr++;
213 } while (--count > 0);
216 *destptr ^= (*destptr ^ *srcptr) & (uintD)(bit(count1)-1);
219 std::size_t i = destindex - srcindex;
221 if (destindex >= srcindex) { // i > 0
222 if (count <= intDsize-destindex) {
223 *destptr ^= (*destptr ^ (*srcptr << i)) & ((uintD)(bit(count)-1) << destindex);
226 *destptr ^= (*destptr ^ (*srcptr << i)) & (uintD)minus_bit(destindex);
228 tmp = *srcptr >> (intDsize-i);
229 count -= intDsize-destindex;
231 if (count <= intDsize-srcindex) {
232 *destptr ^= (*destptr ^ (*srcptr >> -i)) & ((uintD)(bit(count)-1) << destindex);
235 tmp = (*destptr & (uintD)(bit(destindex)-1)) | ((*srcptr >> srcindex) << destindex);
240 // tmp now contains the low i bits to be put into *destptr.
241 std::size_t count1 = count%intDsize;
242 count = floor(count,intDsize);
247 lastdest = shiftleftcopy_loop_up(srcptr,destptr,count,i);
250 // lastdest now contains the i bits shifted out of the top of the source.
254 lastdest |= *(srcptr += count) << i;
255 *destptr ^= (*destptr ^ lastdest) & (uintD)(bit(count1)-1);
261 // It would be most natural to use the following type for uint_t:
262 // m = 1: uint_t = uint8
263 // m = 2: uint_t = uint8
264 // m = 4: uint_t = uint8
265 // m = 8: uint_t = uint8
266 // m = 16: uint_t = uint16
267 // m = 32: uint_t = uint32
268 // But we want to have a fast copy_elements routine. And for m=1,
269 // we also want to use the fast shiftxor_loop_up() function for addition.
270 // Hence we use the uint_t = uintD in all cases. (NB: intDsize>=32.)
272 // The last ceiling(len*m/intDsize)*intDsize-len*m unused bits in the last word
273 // are always 0. This provides some simplification for routines which work on
274 // entire words: They don't need to special-case the last word.
277 DEFINE_cl_heap_GV_I_bits(1,uintD)
279 static const cl_I bits1_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
281 return (unsigned int)((((const cl_heap_GV_I_bits1 *) outcast(vec))->data[index/intDsize] >> (index%intDsize)) & 0x1);
283 static void bits1_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
289 uintD* ptr = &((cl_heap_GV_I_bits1 *) outcast(vec))->data[index/intDsize];
290 index = index%intDsize;
291 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0x1 << index));
295 throw runtime_exception();
299 DEFINE_cl_heap_GV_I_bits(2,uintD)
301 static const cl_I bits2_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
303 return (unsigned int)((((const cl_heap_GV_I_bits2 *) outcast(vec))->data[index/(intDsize/2)] >> (2*(index%(intDsize/2)))) & 0x3);
305 static void bits2_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
311 uintD* ptr = &((cl_heap_GV_I_bits2 *) outcast(vec))->data[index/(intDsize/2)];
312 index = 2*(index%(intDsize/2));
313 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0x3 << index));
317 throw runtime_exception();
321 DEFINE_cl_heap_GV_I_bits(4,uintD)
323 static const cl_I bits4_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
325 return (unsigned int)((((const cl_heap_GV_I_bits4 *) outcast(vec))->data[index/(intDsize/4)] >> (4*(index%(intDsize/4)))) & 0xF);
327 static void bits4_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
333 uintD* ptr = &((cl_heap_GV_I_bits4 *) outcast(vec))->data[index/(intDsize/4)];
334 index = 4*(index%(intDsize/4));
335 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xF << index));
339 throw runtime_exception();
343 DEFINE_cl_heap_GV_I_bits(8,uintD)
345 static const cl_I bits8_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
347 #if CL_CPU_BIG_ENDIAN_P
348 return (unsigned int)((((const cl_heap_GV_I_bits8 *) outcast(vec))->data[index/(intDsize/8)] >> (8*(index%(intDsize/8)))) & 0xFF);
350 // Optimization which assumes little-endian storage of uint8 in an uintD
351 return (unsigned int)(((uint8*)(((const cl_heap_GV_I_bits8 *) outcast(vec))->data))[index]);
354 static void bits8_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
360 #if CL_CPU_BIG_ENDIAN_P
361 uintD* ptr = &((cl_heap_GV_I_bits8 *) outcast(vec))->data[index/(intDsize/8)];
362 index = 8*(index%(intDsize/8));
363 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xFF << index));
365 // Optimization which assumes little-endian storage of uint8 in an uintD
366 ((uint8*)(((cl_heap_GV_I_bits8 *) outcast(vec))->data))[index] = xval;
371 throw runtime_exception();
375 DEFINE_cl_heap_GV_I_bits(16,uintD)
377 static const cl_I bits16_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
379 #if CL_CPU_BIG_ENDIAN_P
380 return (unsigned int)((((const cl_heap_GV_I_bits16 *) outcast(vec))->data[index/(intDsize/16)] >> (16*(index%(intDsize/16)))) & 0xFFFF);
382 // Optimization which assumes little-endian storage of uint16 in an uintD
383 return (unsigned int)(((uint16*)(((const cl_heap_GV_I_bits16 *) outcast(vec))->data))[index]);
386 static void bits16_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
391 if (xval <= 0xFFFF) {
392 #if CL_CPU_BIG_ENDIAN_P
393 uintD* ptr = &((cl_heap_GV_I_bits16 *) outcast(vec))->data[index/(intDsize/16)];
394 index = 16*(index%(intDsize/16));
395 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xFFFF << index));
397 // Optimization which assumes little-endian storage of uint16 in an uintD
398 ((uint16*)(((cl_heap_GV_I_bits16 *) outcast(vec))->data))[index] = xval;
403 throw runtime_exception();
407 DEFINE_cl_heap_GV_I_bits(32,uintD)
409 static const cl_I bits32_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
412 return (unsigned long)(((const cl_heap_GV_I_bits32 *) outcast(vec))->data[index]);
413 #elif CL_CPU_BIG_ENDIAN_P
414 return (unsigned long)((((const cl_heap_GV_I_bits32 *) outcast(vec))->data[index/(intDsize/32)] >> (32*(index%(intDsize/32)))) & 0xFFFFFFFF);
416 // Optimization which assumes little-endian storage of uint32 in an uintD
417 return (unsigned long)(((uint32*)(((const cl_heap_GV_I_bits32 *) outcast(vec))->data))[index]);
420 static void bits32_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
422 uint32 xval = cl_I_to_UL(x);
424 ((cl_heap_GV_I_bits32 *) outcast(vec))->data[index] = xval;
425 #elif CL_CPU_BIG_ENDIAN_P
426 uintD* ptr = &((cl_heap_GV_I_bits32 *) outcast(vec))->data[index/(intDsize/32)];
427 index = 32*(index%(intDsize/32));
428 *ptr = *ptr ^ ((*ptr ^ ((uintD)xval << index)) & ((uintD)0xFFFFFFFF << index));
430 // Optimization which assumes little-endian storage of uint32 in an uintD
431 ((uint32*)(((cl_heap_GV_I_bits32 *) outcast(vec))->data))[index] = xval;
436 static cl_GV_I_vectorops* bits_vectorops[6] = {
445 cl_heap_GV_I* cl_make_heap_GV_I (std::size_t len, sintC m)
447 // Determine log2(bits).
451 log2_bits = 0; break;
453 log2_bits = 1; break;
455 log2_bits = 2; break;
456 case 5: case 6: case 7: case 8:
457 log2_bits = 3; break;
458 case 9: case 10: case 11: case 12:
459 case 13: case 14: case 15: case 16:
460 log2_bits = 4; break;
461 case 17: case 18: case 19: case 20:
462 case 21: case 22: case 23: case 24:
463 case 25: case 26: case 27: case 28:
464 case 29: case 30: case 31: case 32:
465 log2_bits = 5; break;
467 return cl_make_heap_GV_I(len);
469 // For room allocation purposes, be pessimistic: assume the uintD case (since intDsize>=32).
470 std::size_t words = // ceiling(len*2^log2_bits,intDsize)
471 (((sintC)len-1)>>(log2_intDsize-log2_bits))+1;
472 cl_heap_GV_I_bits32* hv = (cl_heap_GV_I_bits32*) malloc_hook(offsetofa(cl_heap_GV_I_bits32,data)+sizeof(uintD)*words);
474 hv->type = &cl_class_gvector_integer();
475 new (&hv->v) cl_GV_inner<cl_I> (len,&bits_vectorops[log2_bits]->ops);
476 uintD* ptr = (uintD*)(hv->data);
477 for (std::size_t i = 0; i < words; i++)
479 return (cl_heap_GV_I*) hv;
483 sintC cl_heap_GV_I::maxbits () const
485 return outcast(v.vectorops)->m;
490 const cl_GV_I cl_null_GV_I = cl_null_GV_I;
492 int cl_GV_I_init_helper::count = 0;
494 cl_GV_I_init_helper::cl_GV_I_init_helper()
497 new ((void *)&cl_null_GV_I) cl_GV_I((std::size_t)0);
500 cl_GV_I_init_helper::~cl_GV_I_init_helper()
503 // Nothing to clean up