src/lua/bit.cpp

   1 #include "lua/internal.hpp"
   2 #include "library/minmax.hpp"
   3 #include "library/int24.hpp"
   4 #include "library/serialization.hpp"
   5
   6 namespace
   7 {
   8         template<unsigned nbits>
   9         uint64_t maskn()
  10         {
  11                 if(nbits > 63)
  12                         return 0xFFFFFFFFFFFFFFFFULL;
  13                 else
  14                         return (1ULL << (nbits&63)) - 1;
  15         }
  16
  17         uint64_t maskx(unsigned nbits)
  18         {
  19                 if(nbits > 63)
  20                         return 0xFFFFFFFFFFFFFFFFULL;
  21                 else
  22                         return (1ULL << (nbits&63)) - 1;
  23         }
  24
  25         template<unsigned nbits>
  26         uint64_t combine_none(uint64_t chain, uint64_t arg)
  27         {
  28                 return (chain & ~arg) & maskn<nbits>();
  29         }
  30
  31         template<unsigned nbits>
  32         uint64_t combine_any(uint64_t chain, uint64_t arg)
  33         {
  34                 return (chain | arg) & maskn<nbits>();
  35         }
  36
  37         template<unsigned nbits>
  38         uint64_t combine_all(uint64_t chain, uint64_t arg)
  39         {
  40                 return (chain & arg) & maskn<nbits>();
  41         }
  42
  43         template<unsigned nbits>
  44         uint64_t combine_parity(uint64_t chain, uint64_t arg)
  45         {
  46                 return (chain ^ arg) & maskn<nbits>();
  47         }
  48
  49         template<unsigned nbits>
  50         uint64_t shift_lrotate(uint64_t base, uint64_t amount, uint64_t bits)
  51         {
  52                 uint64_t mask = maskx(bits);
  53                 base &= mask;
  54                 base = (base << amount) | (base >> (bits - amount));
  55                 return base & mask & maskn<nbits>();
  56         }
  57
  58         template<unsigned nbits>
  59         uint64_t shift_rrotate(uint64_t base, uint64_t amount, uint64_t bits)
  60         {
  61                 uint64_t mask = maskx(bits);
  62                 base &= mask;
  63                 base = (base >> amount) | (base << (bits - amount));
  64                 return base & mask & maskn<nbits>();
  65         }
  66
  67         template<unsigned nbits>
  68         uint64_t shift_lshift(uint64_t base, uint64_t amount, uint64_t bits)
  69         {
  70                 uint64_t mask = maskx(bits);
  71                 base <<= amount;
  72                 return base & mask & maskn<nbits>();
  73         }
  74
  75         template<unsigned nbits>
  76         uint64_t shift_lrshift(uint64_t base, uint64_t amount, uint64_t bits)
  77         {
  78                 uint64_t mask = maskx(bits);
  79                 base &= mask;
  80                 base >>= amount;
  81                 return base & maskn<nbits>();
  82         }
  83
  84         template<unsigned nbits>
  85         uint64_t shift_arshift(uint64_t base, uint64_t amount, uint64_t bits)
  86         {
  87                 uint64_t mask = maskx(bits);
  88                 base &= mask;
  89                 bool negative = ((base >> (bits - 1)) != 0);
  90                 base >>= amount;
  91                 base |= ((negative ? maskn<nbits>() : 0) << (bits - amount));
  92                 return base & mask & maskn<nbits>();
  93         }
  94
  95         uint64_t zero()
  96         {
  97                 return 0;
  98         }
  99
 100         template<unsigned nbits>
 101         uint64_t ones()
 102         {
 103                 return maskn<nbits>();
 104         }
 105
 106         template<uint64_t (*combine)(uint64_t chain, uint64_t arg), uint64_t (*init)()>
 107         int fold(lua::state& L, lua::parameters& P)
 108         {
 109                 uint64_t ret = init();
 110                 while(P.more())
 111                         ret = combine(ret, P.arg<uint64_t>());
 112                 L.pushnumber(ret);
 113                 return 1;
 114         }
 115
 116         template<uint64_t (*sh)(uint64_t base, uint64_t amount, uint64_t bits), unsigned nbits>
 117         int shift(lua::state& L, lua::parameters& P)
 118         {
 119                 uint64_t base, amount, bits;
 120
 121                 P(base, P.optional(amount, 1), P.optional(bits, nbits));
 122
 123                 L.pushnumber(sh(base, amount, bits));
 124                 return 1;
 125         }
 126
 127         template<typename T>
 128         int bswap(lua::state& L, lua::parameters& P)
 129         {
 130                 T val;
 131
 132                 P(val);
 133
 134                 serialization::swap_endian(val);
 135                 L.pushnumber(val);
 136                 return 1;
 137         }
 138
 139         int bit_extract(lua::state& L, lua::parameters& P)
 140         {
 141                 uint64_t ret = 0;
 142                 uint64_t num;
 143
 144                 P(num);
 145
 146                 for(size_t i = 0;; i++) {
 147                         if(P.is_boolean()) {
 148                                 if(P.arg<bool>())
 149                                         ret |= (1ULL << i);
 150                         } else if(P.is_number()) {
 151                                 ret |= (((num >> P.arg<uint8_t>()) & 1) << i);
 152                         } else
 153                                 break;
 154                 }
 155                 L.pushnumber(ret);
 156                 return 1;
 157         }
 158
 159         int bit_value(lua::state& L, lua::parameters& P)
 160         {
 161                 uint64_t ret = 0;
 162                 for(size_t i = 0;; i++) {
 163                         if(P.is_number()) {
 164                                 ret |= (1ULL << P.arg<uint8_t>());
 165                         } else if(P.is_nil()) {
 166                         } else
 167                                 break;
 168                 }
 169                 L.pushnumber(ret);
 170                 return 1;
 171         }
 172
 173         template<bool all>
 174         int bit_test(lua::state& L, lua::parameters& P)
 175         {
 176                 uint64_t a, b;
 177
 178                 P(a, b);
 179
 180                 uint64_t t = a & b;
 181                 bool c = all ? (t == b) : (t != 0);
 182                 L.pushboolean(c);
 183                 return 1;
 184         }
 185
 186         template<bool complement>
 187         int bit_test2(lua::state& L, lua::parameters& P)
 188         {
 189                 uint64_t a, b;
 190
 191                 P(a, b);
 192
 193                 uint64_t t = a & (1ULL << b);
 194                 L.pushboolean((t != 0) != complement);
 195                 return 1;
 196         }
 197
 198         const int CONST_poptable[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
 199
 200         int popcount(uint64_t x)
 201         {
 202                 int c = 0;
 203                 for(unsigned i = 0; i < 16; i++) {
 204                         c += CONST_poptable[x & 15];
 205                         x >>= 4;
 206                 }
 207                 return c;
 208         }
 209
 210         int bit_popcount(lua::state& L, lua::parameters& P)
 211         {
 212                 uint64_t a;
 213
 214                 P(a);
 215
 216                 L.pushnumber(popcount(a));
 217                 return 1;
 218         }
 219
 220         template<bool right, unsigned nbits>
 221         int bit_cshift(lua::state& L, lua::parameters& P)
 222         {
 223                 uint64_t a, b;
 224                 unsigned amount, bits;
 225
 226                 P(a, b, P.optional(amount, 1), P.optional(bits, nbits));
 227
 228                 uint64_t mask = maskx(bits);
 229                 a &= mask;
 230                 b &= mask;
 231                 if(right) {
 232                         b >>= amount;
 233                         b |= (a << (bits - amount));
 234                         b &= mask;
 235                         a >>= amount;
 236                 } else {
 237                         a <<= amount;
 238                         a &= mask;
 239                         a |= (b >> (bits - amount));
 240                         b <<= amount;
 241                         b &= mask;
 242                 }
 243                 L.pushnumber(a);
 244                 L.pushnumber(b);
 245                 return 2;
 246         }
 247
 248         template<bool reverse>
 249         int flagdecode_core(lua::state& L, lua::parameters& P)
 250         {
 251                 uint64_t a, b;
 252                 std::string on, off;
 253
 254                 P(a, b, P.optional(on, ""), P.optional(off, ""));
 255
 256                 auto on32 = utf8::to32(on);
 257                 auto off32 = utf8::to32(off);
 258
 259                 size_t onl = on32.length();
 260                 size_t offl = off32.length();
 261                 auto onc = onl ? on32[onl - 1] : '*';
 262                 auto offc = offl ? off32[offl - 1] : '-';
 263                 char32_t buffer[65];
 264                 unsigned i;
 265                 size_t bias = min(b, (uint64_t)64) - 1;
 266                 for(i = 0; i < 64 && i < b; i++) {
 267                         auto onc2 = (i < onl) ? on32[i] : onc;
 268                         auto offc2 = (i < offl) ? off32[i] : offc;
 269                         buffer[reverse ? (bias - i) : i] = ((a >> i) & 1) ? onc2 : offc2;
 270                 }
 271                 buffer[i] = '\0';
 272                 L.pushlstring(utf8::to8(buffer));
 273                 return 1;
 274         }
 275
 276         int bit_compose(lua::state& L, lua::parameters& P)
 277         {
 278                 uint64_t res = 0;
 279                 uint8_t shift = 0;
 280                 while(P.more()) {
 281                         uint64_t t;
 282                         P(t);
 283                         res |= (t << shift);
 284                         shift += 8;
 285                 }
 286                 L.pushnumber(res);
 287                 return 1;
 288         }
 289
 290         template<typename T, bool littleendian>
 291         int bit_ldbinarynumber(lua::state& L, lua::parameters& P)
 292         {
 293                 size_t pos;
 294                 const char* str;
 295                 size_t len;
 296
 297                 str = L.tolstring(P.skip(), len);
 298                 P(pos);
 299
 300                 if(pos + sizeof(T) > len)
 301                         throw std::runtime_error(P.get_fname() + ": Offset out of range");
 302
 303                 L.pushnumber(serialization::read_endian<T>(str + pos, littleendian ? -1 : 1));
 304                 return 1;
 305         }
 306
 307         template<typename T, bool littleendian>
 308         int bit_stbinarynumber(lua::state& L, lua::parameters& P)
 309         {
 310                 T val;
 311                 char buffer[sizeof(T)];
 312
 313                 P(val);
 314
 315                 serialization::write_endian<T>(buffer, val, littleendian ? -1 : 1);
 316                 L.pushlstring(buffer, sizeof(T));
 317                 return 1;
 318         }
 319
 320         int bit_quotent(lua::state& L, lua::parameters& P)
 321         {
 322                 int64_t a, b;
 323
 324                 P(a, b);
 325
 326                 L.pushnumber(a / b);
 327                 return 1;
 328         }
 329
 330         int bit_multidiv(lua::state& L, lua::parameters& P)
 331         {
 332                 double v;
 333                 unsigned values = L.gettop();
 334
 335                 P(v);
 336
 337                 for(unsigned i = 1; i < values; i++) {
 338                         int64_t q;
 339                         P(q);
 340                         int64_t qx = v / q;
 341                         L.pushnumber(qx);
 342                         v -= qx * q;
 343                 }
 344                 L.pushnumber(v);
 345                 return values;
 346         };
 347
 348         int bit_mul32(lua::state& L, lua::parameters& P)
 349         {
 350                 uint32_t a, b;
 351                 uint64_t c;
 352
 353                 P(a, b);
 354
 355                 c = (uint64_t)a * b;
 356                 L.pushnumber(c & 0xFFFFFFFFU);
 357                 L.pushnumber(c >> 32);
 358                 return 2;
 359         }
 360
 361         int bit_fextract(lua::state& L, lua::parameters& P)
 362         {
 363                 uint64_t a, b, c;
 364
 365                 P(a, b, c);
 366                 if(b > 63)
 367                         L.pushnumber(0);
 368                 else if(c > 63)
 369                         L.pushnumber(a >> b);
 370                 else
 371                         L.pushnumber((a >> b) & ((1 << c) - 1));
 372                 return 1;
 373         }
 374
 375         int bit_bfields(lua::state& L, lua::parameters& P)
 376         {
 377                 uint64_t v;
 378                 unsigned values = L.gettop();
 379
 380                 P(v);
 381                 for(unsigned i = 1; i < values; i++) {
 382                         uint64_t q;
 383                         P(q);
 384                         if(q > 63) {
 385                                 L.pushnumber(v);
 386                                 v = 0;
 387                         } else {
 388                                 L.pushnumber(v & ((1 << q) - 1));
 389                                 v >>= q;
 390                         }
 391                 }
 392                 return values - 1;
 393         }
 394
 395         lua::functions LUA_bitops_fn(lua_func_bit, "bit", {
 396                 {"flagdecode", flagdecode_core<false>},
 397                 {"rflagdecode", flagdecode_core<true>},
 398                 {"none", fold<combine_none<48>, ones<48>>},
 399                 {"any", fold<combine_any<48>, zero>},
 400                 {"all", fold<combine_all<48>, ones<48>>},
 401                 {"parity", fold<combine_parity<48>, zero>},
 402                 {"bnot", fold<combine_none<48>, ones<48>>},
 403                 {"bor", fold<combine_any<48>, zero>},
 404                 {"band", fold<combine_all<48>, ones<48>>},
 405                 {"bxor", fold<combine_parity<48>, zero>},
 406                 {"lrotate", shift<shift_lrotate<48>, 48>},
 407                 {"rrotate", shift<shift_rrotate<48>, 48>},
 408                 {"lshift", shift<shift_lshift<48>, 48>},
 409                 {"arshift", shift<shift_arshift<48>, 48>},
 410                 {"lrshift", shift<shift_lrshift<48>, 48>},
 411 #ifdef LUA_SUPPORTS_INTEGERS
 412                 {"wnone", fold<combine_none<64>, ones<64>>},
 413                 {"wany", fold<combine_any<64>, zero>},
 414                 {"wall", fold<combine_all<64>, ones<64>>},
 415                 {"wparity", fold<combine_parity<64>, zero>},
 416                 {"wbnot", fold<combine_none<64>, ones<64>>},
 417                 {"wbor", fold<combine_any<64>, zero>},
 418                 {"wband", fold<combine_all<64>, ones<64>>},
 419                 {"wbxor", fold<combine_parity<64>, zero>},
 420                 {"wlrotate", shift<shift_lrotate<64>, 64>},
 421                 {"wrrotate", shift<shift_rrotate<64>, 64>},
 422                 {"wlshift", shift<shift_lshift<64>, 64>},
 423                 {"warshift", shift<shift_arshift<64>, 64>},
 424                 {"wlrshift", shift<shift_lrshift<64>, 64>},
 425                 {"wclshift", bit_cshift<false, 64>},
 426                 {"wcrshift", bit_cshift<true, 64>},
 427 #endif
 428                 {"swapword", bswap<uint16_t>},
 429                 {"swaphword", bswap<ss_uint24_t>},
 430                 {"swapdword", bswap<uint32_t>},
 431                 {"swapqword", bswap<uint64_t>},
 432                 {"swapsword", bswap<int16_t>},
 433                 {"swapshword", bswap<ss_int24_t>},
 434                 {"swapsdword", bswap<int32_t>},
 435                 {"swapsqword", bswap<int64_t>},
 436                 {"extract", bit_extract},
 437                 {"value", bit_value},
 438                 {"test_any", bit_test<false>},
 439                 {"test_all", bit_test<true>},
 440                 {"test", bit_test2<false>},
 441                 {"testn", bit_test2<true>},
 442                 {"popcount", bit_popcount},
 443                 {"clshift", bit_cshift<false, 48>},
 444                 {"crshift", bit_cshift<true, 48>},
 445                 {"compose", bit_compose},
 446                 {"quotent", bit_quotent},
 447                 {"multidiv", bit_multidiv},
 448                 {"mul32", bit_mul32},
 449                 {"fextract", bit_fextract},
 450                 {"bfields", bit_bfields},
 451                 {"binary_ld_u8be", bit_ldbinarynumber<uint8_t, false>},
 452                 {"binary_ld_s8be", bit_ldbinarynumber<int8_t, false>},
 453                 {"binary_ld_u16be", bit_ldbinarynumber<uint16_t, false>},
 454                 {"binary_ld_s16be", bit_ldbinarynumber<int16_t, false>},
 455                 {"binary_ld_u24be", bit_ldbinarynumber<ss_uint24_t, false>},
 456                 {"binary_ld_s24be", bit_ldbinarynumber<ss_int24_t, false>},
 457                 {"binary_ld_u32be", bit_ldbinarynumber<uint32_t, false>},
 458                 {"binary_ld_s32be", bit_ldbinarynumber<int32_t, false>},
 459                 {"binary_ld_u64be", bit_ldbinarynumber<uint64_t, false>},
 460                 {"binary_ld_s64be", bit_ldbinarynumber<int64_t, false>},
 461                 {"binary_ld_floatbe", bit_ldbinarynumber<float, false>},
 462                 {"binary_ld_doublebe", bit_ldbinarynumber<double, false>},
 463                 {"binary_ld_u8le", bit_ldbinarynumber<uint8_t, true>},
 464                 {"binary_ld_s8le", bit_ldbinarynumber<int8_t, true>},
 465                 {"binary_ld_u16le", bit_ldbinarynumber<uint16_t, true>},
 466                 {"binary_ld_s16le", bit_ldbinarynumber<int16_t, true>},
 467                 {"binary_ld_u24le", bit_ldbinarynumber<ss_uint24_t, true>},
 468                 {"binary_ld_s24le", bit_ldbinarynumber<ss_int24_t, true>},
 469                 {"binary_ld_u32le", bit_ldbinarynumber<uint32_t, true>},
 470                 {"binary_ld_s32le", bit_ldbinarynumber<int32_t, true>},
 471                 {"binary_ld_u64le", bit_ldbinarynumber<uint64_t, true>},
 472                 {"binary_ld_s64le", bit_ldbinarynumber<int64_t, true>},
 473                 {"binary_ld_floatle", bit_ldbinarynumber<float, true>},
 474                 {"binary_ld_doublele", bit_ldbinarynumber<double, true>},
 475                 {"binary_st_u8be", bit_stbinarynumber<uint8_t, false>},
 476                 {"binary_st_s8be", bit_stbinarynumber<int8_t, false>},
 477                 {"binary_st_u16be", bit_stbinarynumber<uint16_t, false>},
 478                 {"binary_st_s16be", bit_stbinarynumber<int16_t, false>},
 479                 {"binary_st_u24be", bit_stbinarynumber<ss_uint24_t, false>},
 480                 {"binary_st_s24be", bit_stbinarynumber<ss_int24_t, false>},
 481                 {"binary_st_u32be", bit_stbinarynumber<uint32_t, false>},
 482                 {"binary_st_s32be", bit_stbinarynumber<int32_t, false>},
 483                 {"binary_st_u64be", bit_stbinarynumber<uint64_t, false>},
 484                 {"binary_st_s64be", bit_stbinarynumber<int64_t, false>},
 485                 {"binary_st_floatbe", bit_stbinarynumber<float, false>},
 486                 {"binary_st_doublebe", bit_stbinarynumber<double, false>},
 487                 {"binary_st_u8le", bit_stbinarynumber<uint8_t, true>},
 488                 {"binary_st_s8le", bit_stbinarynumber<int8_t, true>},
 489                 {"binary_st_u16le", bit_stbinarynumber<uint16_t, true>},
 490                 {"binary_st_s16le", bit_stbinarynumber<int16_t, true>},
 491                 {"binary_st_u24le", bit_stbinarynumber<ss_uint24_t, true>},
 492                 {"binary_st_s24le", bit_stbinarynumber<ss_int24_t, true>},
 493                 {"binary_st_u32le", bit_stbinarynumber<uint32_t, true>},
 494                 {"binary_st_s32le", bit_stbinarynumber<int32_t, true>},
 495                 {"binary_st_u64le", bit_stbinarynumber<uint64_t, true>},
 496                 {"binary_st_s64le", bit_stbinarynumber<int64_t, true>},
 497                 {"binary_st_floatle", bit_stbinarynumber<float, true>},
 498                 {"binary_st_doublele", bit_stbinarynumber<double, true>},
 499         });
 500 }