Ignore:
Timestamp:
Oct 22, 2011, 2:14:12 PM (8 years ago)
Author:
ksherdy
Message:

Add count_forward_zeroes, count_backward_zeroes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock128.hpp

    r1542 r1550  
    11/*
    2     bitblock128 - 128 bit block size - Specific 128 bit implementations.
     2    bitblock128 - Specific 128 bit IDISA implementations.
    33
    44    Idealized SIMD Operations with SSE versions
     
    1212#define BITBLOCK128_HPP_
    1313
     14#include "idisa128.hpp"
     15
     16union ubitblock128 {
     17        bitblock128_t _128;
     18        uint64_t _64[sizeof(bitblock128_t)/sizeof(uint64_t)];
     19        uint32_t _32[sizeof(bitblock128_t)/sizeof(uint32_t)];
     20        uint16_t _16[sizeof(bitblock128_t)/sizeof(uint16_t)];
     21        uint8_t _8[sizeof(bitblock128_t)/sizeof(uint8_t)];
     22};
     23
    1424static IDISA_ALWAYS_INLINE void adc(bitblock128_t x, bitblock128_t y, bitblock128_t & carry, bitblock128_t & sum);
    1525static IDISA_ALWAYS_INLINE void sbb(bitblock128_t x, bitblock128_t y, bitblock128_t & borrow, bitblock128_t & difference);
     
    2030static IDISA_ALWAYS_INLINE bitblock128_t convert (uint64_t s);
    2131static IDISA_ALWAYS_INLINE uint64_t convert (bitblock128_t v);
     32static IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(bitblock128_t v);
     33static IDISA_ALWAYS_INLINE uint32_t count_backward_zeroes(bitblock128_t v);
     34
    2235
    2336IDISA_ALWAYS_INLINE void adc(bitblock128_t x, bitblock128_t y, bitblock128_t & carry, bitblock128_t & sum)
     
    2538        bitblock128_t gen = simd_and(x, y);
    2639        bitblock128_t prop = simd_or(x, y);
    27         bitblock128_t partial = simd<64>::add(simd<64>::add(x, y), carry);
    28         bitblock128_t c1 = simd128<128>::slli<64>(simd<64>::srli<63>(simd_or(gen, simd_andc(prop, partial))));
    29         sum = simd<64>::add(c1, partial);
     40        bitblock128_t partial = simd128<64>::add(simd128<64>::add(x, y), carry);
     41        bitblock128_t c1 = simd128<128>::slli<64>(simd128<64>::srli<63>(simd_or(gen, simd_andc(prop, partial))));
     42        sum = simd128<64>::add(c1, partial);
    3043        // carry = simd_and(hibitmask<bitblock128_t>(), simd_or(gen, simd_andc(prop, sum))); // TODO - set high bit carry via hibitmask
    3144        carry = simd128<128>::srli<127>(simd_or(gen, simd_andc(prop, sum))); // TODO -
     
    3649        bitblock128_t gen = simd_andc(y, x);
    3750        bitblock128_t prop = simd_not(simd_xor(x, y));
    38         bitblock128_t partial = simd<64>::sub(simd<64>::sub(x, y), borrow);
    39         bitblock128_t b1 = simd128<128>::slli<64>(simd<64>::srli<63>(simd_or(gen, simd_and(prop, partial))));
    40         difference = simd<64>::sub(partial, b1);
     51        bitblock128_t partial = simd128<64>::sub(simd128<64>::sub(x, y), borrow);
     52        bitblock128_t b1 = simd128<128>::slli<64>(simd128<64>::srli<63>(simd_or(gen, simd_and(prop, partial))));
     53        difference = simd128<64>::sub(partial, b1);
    4154        // borrow = simd_and(hibitmask<bitblock128_t>, simd_or(gen, simd_and(prop, difference))); // TODO - set high bit carry via hibitmask
    4255        borrow = simd128<128>::srli<127>(simd_or(gen, simd_and(prop, difference)));
     
    4558IDISA_ALWAYS_INLINE void advance_with_carry(bitblock128_t cursor, bitblock128_t & carry, bitblock128_t & rslt)
    4659{
    47 bitblock128_t shift_out = simd<64>::srli<63>(cursor);
    48 bitblock128_t low_bits = esimd<64>::mergel(shift_out, carry);
     60bitblock128_t shift_out = simd128<64>::srli<63>(cursor);
     61bitblock128_t low_bits = esimd128<64>::mergel(shift_out, carry);
    4962// carry = simd_and(hibitmask<bitblock128_t>, cursor);
    5063carry = simd128<128>::srli<64>(shift_out);                                              // carry - accumlated 127 shift right locical shift of cursor
    51 rslt = simd_or(simd<64>::add(cursor, cursor), low_bits);
     64rslt = simd_or(simd128<64>::add(cursor, cursor), low_bits);
    5265}
    5366
    5467IDISA_ALWAYS_INLINE bool bitblock_has_bit(bitblock128_t arg1)
    5568{
    56         // TOOD simd128::any(arg1);
    5769        return bitblock::any(arg1);
    5870}
     
    6072IDISA_ALWAYS_INLINE uint64_t bitblock_bit_count(bitblock128_t arg1)
    6173{
    62         // TODO simd128::popcount(arg1)
    63         return mvmd<64>::extract<0>(simd128<128>::popcount(arg1));
     74        return mvmd128<64>::extract<0>(simd128<128>::popcount(arg1));
    6475}
    6576
    6677IDISA_ALWAYS_INLINE void signbitmask(bitblock128_t & v)
    6778{
    68         // TODO simd128::
    6979        v =  simd128<128>::slli<127>(simd128<128>::constant<1>());
    7080}
    71 
    72 /* Type conversion support */
    73 union ubitblock128 {
    74         //bitblock256_t 256;
    75         bitblock128_t _128;
    76         uint64_t _64[sizeof(bitblock128_t)/sizeof(uint64_t)];
    77         uint32_t _32[sizeof(bitblock128_t)/sizeof(uint32_t)];
    78         uint16_t _16[sizeof(bitblock128_t)/sizeof(uint16_t)];
    79         uint8_t _8[sizeof(bitblock128_t)/sizeof(uint8_t)];
    80 };
    8181
    8282IDISA_ALWAYS_INLINE bitblock128_t convert(uint64_t s)
     
    8989IDISA_ALWAYS_INLINE uint64_t convert (bitblock128_t v)
    9090{
    91         return (uint64_t) mvmd<64>::extract<0>(v);
     91        return (uint64_t) mvmd128<64>::extract<0>(v);
    9292}
    9393
     94IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(bitblock128_t v) {
     95        union {bitblock128_t bitblock; unsigned long elems[sizeof(bitblock128_t)/sizeof(long)];} u;
     96        u.bitblock = v;
     97
     98#if LONG_BIT == 64
     99  if (u.elems[0] != 0) {return cfzll(u.elems[0]);}
     100  else if (u.elems[1] != 0) {return 64 + cfzll(u.elems[1]);}
     101  else {return 128;}
     102#endif
     103
     104#if LONG_BIT < 64
     105  if (u.elems[0] != 0) {return cfzl(u.elems[0]);}
     106  else if (u.elems[1] != 0) {return 32 + cfzl(u.elems[1]);}
     107  else if (u.elems[2] != 0) {return 64 + cfzl(u.elems[2]);}
     108  else if (u.elems[3] != 0) {return 96 + cfzl(u.elems[3]);}
     109#endif
     110  else {return 128;}
     111}
     112
     113IDISA_ALWAYS_INLINE uint32_t count_backward_zeroes(bitblock128_t v) {
     114        union {bitblock128_t bitblock; unsigned long elems[sizeof(bitblock128_t)/sizeof(long)];} u;
     115        u.bitblock = v;
     116
     117#if LONG_BIT == 64
     118  if (u.elems[1] != 0) return cbzll(u.elems[1]);
     119  else if (u.elems[0] != 0) return LONG_BIT + cbzll(u.elems[0]);
     120#endif
     121#if LONG_BIT < 64
     122  if (u.elems[3] != 0) return cbzl(u.elems[3]);
     123  else if (u.elems[2] != 0) return 32 + cbzl(u.elems[2]);
     124  else if (u.elems[1] != 0) return 64 + cbzl(u.elems[1]);
     125  else if (u.elems[0] != 0) return 96 + cbzl(u.elems[0]);
     126#endif
     127  else {return 128;}
     128}
    94129
    95130#endif /* BITBLOCK128_HPP_ */
Note: See TracChangeset for help on using the changeset viewer.