src/vector/cl_GV_I.cc

   1 // cl_make_heap_GV_I().
   2
   3 // General includes.
   4 #include "base/cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/GV_integer.h"
   8
   9
  10 // Implementation.
  11
  12 #include "integer/cl_I.h"
  13 #include "base/digitseq/cl_DS.h"
  14 #include "cln/exception.h"
  15 #include "base/cl_offsetof.h"
  16
  17 namespace cln {
  18
  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
  22 // vectors.
  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.
  26
  27
  28 static void cl_gvector_integer_destructor (cl_heap* pointer)
  29 {
  30 #if (defined(__mips__) || defined(__mips64__)) && !defined(__GNUC__) // workaround SGI CC bug
  31         (*(cl_heap_GV_I*)pointer).~cl_heap_GV();
  32 #else
  33         (*(cl_heap_GV_I*)pointer).~cl_heap_GV_I();
  34 #endif
  35 }
  36
  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()
  40 {
  41         static cl_class instance = {
  42                 cl_gvector_integer_destructor,
  43                 0
  44         };
  45         return instance;
  46 }
  47
  48 static inline cl_heap_GV_I * outcast (cl_GV_inner<cl_I>* vec)
  49 {
  50         return (cl_heap_GV_I *)((char *) vec - offsetof(cl_heap_GV_I,v));
  51 }
  52 static inline const cl_heap_GV_I * outcast (const cl_GV_inner<cl_I>* vec)
  53 {
  54         return (const cl_heap_GV_I *)((const char *) vec - offsetof(cl_heap_GV_I,v));
  55 }
  56
  57
  58 // Add more info to the vectorops tables.
  59
  60 struct cl_GV_I_vectorops {
  61         cl_GV_vectorops<cl_I> ops;
  62         sintC m; // for maxbits
  63 };
  64
  65 static inline cl_GV_I_vectorops* outcast (cl_GV_vectorops<cl_I>* vectorops)
  66 {
  67         return (cl_GV_I_vectorops*)((char *) vectorops - offsetof(cl_GV_I_vectorops,ops));
  68 }
  69
  70
  71 // Vectors of general integers.
  72
  73 struct cl_heap_GV_I_general : public cl_heap_GV_I {
  74         cl_I data[1];
  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 ();
  81 };
  82
  83 static const cl_I general_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
  84 {
  85         return ((const cl_heap_GV_I_general *) outcast(vec))->data[index];
  86 }
  87
  88 static void general_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
  89 {
  90         ((cl_heap_GV_I_general *) outcast(vec))->data[index] = x;
  91 }
  92
  93 static void general_do_delete (cl_GV_inner<cl_I>* vec)
  94 {
  95         cl_heap_GV_I_general* hv = (cl_heap_GV_I_general *) outcast(vec);
  96         std::size_t len = hv->v.size();
  97         for (std::size_t i = 0; i < len; i++)
  98                 hv->data[i].~cl_I();
  99 }
 100
 101 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)
 102 {
 103         if (count > 0) {
 104                 const cl_heap_GV_I_general* srcv =
 105                   (const cl_heap_GV_I_general *) outcast(srcvec);
 106                 cl_heap_GV_I_general* destv =
 107                   (cl_heap_GV_I_general *) outcast(destvec);
 108                 std::size_t srclen = srcv->v.size();
 109                 std::size_t destlen = destv->v.size();
 110                 if (!(srcindex <= srcindex+count && srcindex+count <= srclen))
 111                         throw runtime_exception();
 112                 if (!(destindex <= destindex+count && destindex+count <= destlen))
 113                         throw runtime_exception();
 114                 do {
 115                         destv->data[destindex++] = srcv->data[srcindex++];
 116                 } while (--count > 0);
 117         }
 118 }
 119
 120 static cl_GV_I_vectorops general_vectorops = {{
 121         general_element,
 122         general_set_element,
 123         general_do_delete,
 124         general_copy_elements },
 125         -1
 126 };
 127
 128 cl_heap_GV_I* cl_make_heap_GV_I (std::size_t len)
 129 {
 130         cl_heap_GV_I_general* hv = (cl_heap_GV_I_general*) malloc_hook(offsetofa(cl_heap_GV_I_general,data)+sizeof(cl_I)*len);
 131         hv->refcount = 1;
 132         hv->type = &cl_class_gvector_integer();
 133         new (&hv->v) cl_GV_inner<cl_I> (len,&general_vectorops.ops);
 134         for (std::size_t i = 0; i < len; i++)
 135                 init1(cl_I, hv->data[i]) ();
 136         return hv;
 137 }
 138
 139
 140 // Vectors of integers requiring only few bits.
 141
 142 #define DEFINE_cl_heap_GV_I_bits(m,uint_t)  \
 143 struct cl_heap_GV_I_bits##m : public cl_heap_GV_I {                     \
 144         uint_t data[1];                                                 \
 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 ();                                        \
 151 };                                                                      \
 152 static const cl_I bits##m##_element (const cl_GV_inner<cl_I>* vec, std::size_t index); \
 153 static void bits##m##_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x); \
 154 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) \
 155 {                                                                               \
 156         if (count > 0) {                                                        \
 157                 const cl_heap_GV_I_bits##m * srcv =                             \
 158                   (const cl_heap_GV_I_bits##m *) outcast(srcvec);               \
 159                 cl_heap_GV_I_bits##m * destv =                                  \
 160                   (cl_heap_GV_I_bits##m *) outcast(destvec);                    \
 161                 std::size_t srclen = srcv->v.size();                            \
 162                 std::size_t destlen = destv->v.size();                          \
 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                         const uintD* srcptr = &srcv->data[srcindex];            \
 169                         uintD* destptr = &destv->data[destindex];               \
 170                         do {                                                    \
 171                                 *destptr++ = *srcptr++;                         \
 172                         } while (--count > 0);                                  \
 173                 } else                                                          \
 174                         bits_copy(srcv->data,m*srcindex,destv->data,m*destindex,m*count); \
 175         }                                                                       \
 176 }                                                                       \
 177 static cl_GV_I_vectorops bits##m##_vectorops = {{                       \
 178         bits##m##_element,                                              \
 179         bits##m##_set_element,                                          \
 180         bits_do_delete,                                                 \
 181         bits##m##_copy_elements },                                      \
 182         m                                                               \
 183 };
 184
 185 static void bits_do_delete (cl_GV_inner<cl_I>* vec)
 186 {
 187         unused vec;
 188 }
 189
 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, std::size_t srcindex, uintD* destptr, std::size_t destindex, std::size_t count)
 193 {
 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.
 201                 if (srcindex > 0) {
 202                         if (count <= intDsize-srcindex) {
 203                                 *destptr ^= (*destptr ^ *srcptr) & ((uintD)(bit(count)-1) << srcindex);
 204                                 return;
 205                         }
 206                         *destptr ^= (*destptr ^ *srcptr) & (uintD)minus_bit(srcindex);
 207                         srcptr++;
 208                         destptr++;
 209                         count -= intDsize-srcindex;
 210                 }
 211                 // Now srcindex and destindex can be assumed to be 0.
 212                 std::size_t count1 = count%intDsize;
 213                 count = floor(count,intDsize);
 214                 if (count > 0) {
 215                         do {
 216                                 *destptr++ = *srcptr++;
 217                         } while (--count > 0);
 218                 }
 219                 if (count1 > 0) {
 220                         *destptr ^= (*destptr ^ *srcptr) & (uintD)(bit(count1)-1);
 221                 }
 222         } else {
 223                 std::size_t i = destindex - srcindex;
 224                 uintD tmp;
 225                 if (destindex >= srcindex) { // i > 0
 226                         if (count <= intDsize-destindex) {
 227                                 *destptr ^= (*destptr ^ (*srcptr << i)) & ((uintD)(bit(count)-1) << destindex);
 228                                 return;
 229                         }
 230                         *destptr ^= (*destptr ^ (*srcptr << i)) & (uintD)minus_bit(destindex);
 231                         destptr++;
 232                         tmp = *srcptr >> (intDsize-i);
 233                         count -= intDsize-destindex;
 234                 } else { // i < 0
 235                         if (count <= intDsize-srcindex) {
 236                                 *destptr ^= (*destptr ^ (*srcptr >> -i)) & ((uintD)(bit(count)-1) << destindex);
 237                                 return;
 238                         }
 239                         tmp = (*destptr & (uintD)(bit(destindex)-1)) | ((*srcptr >> srcindex) << destindex);
 240                         count += destindex;
 241                         i += intDsize;
 242                 }
 243                 srcptr++;
 244                 // tmp now contains the low i bits to be put into *destptr.
 245                 std::size_t count1 = count%intDsize;
 246                 count = floor(count,intDsize);
 247                 uintD lastdest;
 248                 if (count == 0)
 249                         lastdest = tmp;
 250                 else {
 251                         lastdest = shiftleftcopy_loop_up(srcptr,destptr,count,i);
 252                         *destptr |= tmp;
 253                 }
 254                 // lastdest now contains the i bits shifted out of the top of the source.
 255                 if (count1 > 0) {
 256                         destptr += count;
 257                         if (count1 > i)
 258                                 lastdest |= *(srcptr += count) << i;
 259                         *destptr ^= (*destptr ^ lastdest) & (uintD)(bit(count1)-1);
 260                 }
 261         }
 262 }
 263
 264
 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.)
 275
 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.
 279
 280
 281 DEFINE_cl_heap_GV_I_bits(1,uintD)
 282
 283 static const cl_I bits1_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
 284 {
 285         return (unsigned int)((((const cl_heap_GV_I_bits1 *) outcast(vec))->data[index/intDsize] >> (index%intDsize)) & 0x1);
 286 }
 287 static void bits1_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
 288 {
 289         uintV xval;
 290         if (fixnump(x)) {
 291                 xval = FN_to_UV(x);
 292                 if (xval <= 0x1) {
 293                         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));
 296                         return;
 297                 }
 298         }
 299         throw runtime_exception();
 300 }
 301
 302
 303 DEFINE_cl_heap_GV_I_bits(2,uintD)
 304
 305 static const cl_I bits2_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
 306 {
 307         return (unsigned int)((((const cl_heap_GV_I_bits2 *) outcast(vec))->data[index/(intDsize/2)] >> (2*(index%(intDsize/2)))) & 0x3);
 308 }
 309 static void bits2_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
 310 {
 311         uintV xval;
 312         if (fixnump(x)) {
 313                 xval = FN_to_UV(x);
 314                 if (xval <= 0x3) {
 315                         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));
 318                         return;
 319                 }
 320         }
 321         throw runtime_exception();
 322 }
 323
 324
 325 DEFINE_cl_heap_GV_I_bits(4,uintD)
 326
 327 static const cl_I bits4_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
 328 {
 329         return (unsigned int)((((const cl_heap_GV_I_bits4 *) outcast(vec))->data[index/(intDsize/4)] >> (4*(index%(intDsize/4)))) & 0xF);
 330 }
 331 static void bits4_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
 332 {
 333         uintV xval;
 334         if (fixnump(x)) {
 335                 xval = FN_to_UV(x);
 336                 if (xval <= 0xF) {
 337                         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));
 340                         return;
 341                 }
 342         }
 343         throw runtime_exception();
 344 }
 345
 346
 347 DEFINE_cl_heap_GV_I_bits(8,uintD)
 348
 349 static const cl_I bits8_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
 350 {
 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);
 353         #else
 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]);
 356         #endif
 357 }
 358 static void bits8_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
 359 {
 360         uintV xval;
 361         if (fixnump(x)) {
 362                 xval = FN_to_UV(x);
 363                 if (xval <= 0xFF) {
 364                         #if CL_CPU_BIG_ENDIAN_P
 365                         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));
 368                         #else
 369                         // Optimization which assumes little-endian storage of uint8 in an uintD
 370                         ((uint8*)(((cl_heap_GV_I_bits8 *) outcast(vec))->data))[index] = xval;
 371                         #endif
 372                         return;
 373                 }
 374         }
 375         throw runtime_exception();
 376 }
 377
 378
 379 DEFINE_cl_heap_GV_I_bits(16,uintD)
 380
 381 static const cl_I bits16_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
 382 {
 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);
 385         #else
 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]);
 388         #endif
 389 }
 390 static void bits16_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
 391 {
 392         uintV xval;
 393         if (fixnump(x)) {
 394                 xval = FN_to_UV(x);
 395                 if (xval <= 0xFFFF) {
 396                         #if CL_CPU_BIG_ENDIAN_P
 397                         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));
 400                         #else
 401                         // Optimization which assumes little-endian storage of uint16 in an uintD
 402                         ((uint16*)(((cl_heap_GV_I_bits16 *) outcast(vec))->data))[index] = xval;
 403                         #endif
 404                         return;
 405                 }
 406         }
 407         throw runtime_exception();
 408 }
 409
 410
 411 DEFINE_cl_heap_GV_I_bits(32,uintD)
 412
 413 static const cl_I bits32_element (const cl_GV_inner<cl_I>* vec, std::size_t index)
 414 {
 415         #if (intDsize==32)
 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);
 419         #else
 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]);
 422         #endif
 423 }
 424 static void bits32_set_element (cl_GV_inner<cl_I>* vec, std::size_t index, const cl_I& x)
 425 {
 426         uint32 xval = cl_I_to_UL(x);
 427         #if (intDsize==32)
 428         ((cl_heap_GV_I_bits32 *) outcast(vec))->data[index] = xval;
 429         #elif CL_CPU_BIG_ENDIAN_P
 430         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));
 433         #else
 434         // Optimization which assumes little-endian storage of uint32 in an uintD
 435         ((uint32*)(((cl_heap_GV_I_bits32 *) outcast(vec))->data))[index] = xval;
 436         #endif
 437 }
 438
 439
 440 static cl_GV_I_vectorops* bits_vectorops[6] = {
 441         &bits1_vectorops,
 442         &bits2_vectorops,
 443         &bits4_vectorops,
 444         &bits8_vectorops,
 445         &bits16_vectorops,
 446         &bits32_vectorops
 447 };
 448
 449 cl_heap_GV_I* cl_make_heap_GV_I (std::size_t len, sintC m)
 450 {
 451         // Determine log2(bits).
 452         uintL log2_bits;
 453         switch (m) {
 454                 case 0: case 1:
 455                         log2_bits = 0; break;
 456                 case 2:
 457                         log2_bits = 1; break;
 458                 case 3: case 4:
 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;
 470                 default:
 471                         return cl_make_heap_GV_I(len);
 472         }
 473         // For room allocation purposes, be pessimistic: assume the uintD case (since intDsize>=32).
 474         std::size_t words = // ceiling(len*2^log2_bits,intDsize)
 475           (((sintC)len-1)>>(log2_intDsize-log2_bits))+1;
 476         cl_heap_GV_I_bits32* hv = (cl_heap_GV_I_bits32*) malloc_hook(offsetofa(cl_heap_GV_I_bits32,data)+sizeof(uintD)*words);
 477         hv->refcount = 1;
 478         hv->type = &cl_class_gvector_integer();
 479         new (&hv->v) cl_GV_inner<cl_I> (len,&bits_vectorops[log2_bits]->ops);
 480         uintD* ptr = (uintD*)(hv->data);
 481         for (std::size_t i = 0; i < words; i++)
 482                 ptr[i] = 0;
 483         return (cl_heap_GV_I*) hv;
 484 }
 485
 486
 487 sintC cl_heap_GV_I::maxbits () const
 488 {
 489         return outcast(v.vectorops)->m;
 490 }
 491
 492
 493 // An empty vector.
 494 const cl_GV_I cl_null_GV_I = cl_null_GV_I;
 495
 496 int cl_GV_I_init_helper::count = 0;
 497
 498 cl_GV_I_init_helper::cl_GV_I_init_helper()
 499 {
 500         if (count++ == 0)
 501                 new ((void *)&cl_null_GV_I) cl_GV_I((std::size_t)0);
 502 }
 503
 504 cl_GV_I_init_helper::~cl_GV_I_init_helper()
 505 {
 506         if (--count == 0) {
 507                 // Nothing to clean up
 508         }
 509 };
 510
 511 }  // namespace cln
 512